[백준/C++] 기말고사 작품전시 (No. 28094)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 작품마다 순서가 있어서 어떤 작품A가 작품 B보다 앞에 있는 경우 점수 V를 얻는 문제다.

 

여기서 A작품이 B작품이 앞에 있을 경우만 점수 V를 얻으므로, 두 작품을 비교하는 경우를 2차원 vector에 저장해 두고 작품의 순서가 정해지면, 순서가 vector[A][B]의 값을 구하면 된다.

 

그림을 통해 생각해 보면

vector[A][B]는 A가 B보다 앞에 있는 경우 얻는 점수의 총 합이다.

 

그리고 점수를 얻는 경우 중 최대값을 구하고, 그 최대값을 얻는 경우가 총 몇 개인지 출력하면 된다.

 

모든 경우의 수는 재귀를 이용해 구했다.

 

이후 저장된 점수의 최대값과 현재 경우의 점수를 비교해 현재 점수가 더 크면 최대값을 갱신하고 경우의 수를 1로 초기화 한다.

 

만약 최대값과 현재 경우의 점수가 같다면, 경우의 수에 1을 더한다.

 

 

 

​

[아이디어 정리]

1. 2차원 vector를 이용해 [A][B]에 A작품이 B작품보다 앞에 있는 경우 얻을 수 있는 가중치를 저장한다.
2. 재귀 함수를 이용해 모든 경우를 고려해 작품의 순서에 따른 점수를 계산한다.
3. 현재 경우의 점수가 기존의 최대값 보다 크면 최대값을 갱신하고, 개수를 1로 초기화 한다.
4. 현재 경우의 점수가 기존의 최대값과 같다면, 개수를 +1 한다.

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;


int ans, cnt;

void DFS(int deepth, int &N, vector<int> &visited, vector<vector<int>> &cost)
{
	if (deepth == N) //deepth가 순서가 정해진 상태라는 뜻
	{
		int hap = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (visited[i] < visited[j]) {
					hap += cost[i][j];
				}
			}
		}
		if (hap>ans)
		{
			ans = hap;
			cnt = 1;
		}
		else if (hap == ans) {
			cnt += 1;
		}
        return;
	}
	for (int i = 1; i < visited.size(); i++)
	{
		if (visited[i] == -1) {
			visited[i] = deepth;
			DFS(deepth + 1, N, visited, cost);
			visited[i] = -1;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T, N, M;
	cin >> T;
	for (int tc = 0; tc < T; tc++) {
		ans = 0;
		cnt = 0;
		cin >> N >> M;
		vector<vector<int>> cost(N + 1, vector<int>(N + 1, 0)); // [A][B] A가 B보다 앞이라 점수를 얻는 경우
		int A, B, V;
		for (int i = 0; i < M; i++) 
		{
			cin >> V >> A >> B;
			cost[A][B] += V;
		}
		vector<int> visited(N + 1, -1);
		DFS(0, N, visited, cost);
		cout << ans << " " << cnt << "\n";
	}
	return 0;
}

 

---

최악의 경우에 10! * 9 * 9로 제한이 빡빡하다고 생각했는데 의외로 쉽게 통과가 된 문제다.

 

https://www.acmicpc.net/problem/28094