백준 12869번 뮤탈리스크(C++)

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

 

대학 친구의 추천으로 풀어보았다. 처음에는 조합을 순서대로 DFS 넣어보았는데 시간초과가 났다.

 

그리고 고민하다가 문제 분류를 보니 생각지도 못했던 다이나믹 프로그래밍이 보였다. 그걸 보고도 " 엥, 이걸 어캐 DP로 저장하누,,?" 생각했고 부끄럽게도 검색을 통해 아이디어를 가져왔다. DP[a][b][c] 이런 형태로 저장하면 되었다. 

 

즉 이 문제는 dfs + dp 문제이다.

dfs dp는 어렵지만 잘만하면 문제를 깔끔하고 멋지게 풀 수 있다. dfs로 순회하면서 갱신은 dp로 체크하며 더 방문할지 말지 정하는 것이다. 

dfs + dp

dfs + 백트래킹 은 매우 중요하다.  

 

1. -9 -3 -1 순서대로 dfs 순회한다.

2. dp에 저장해둔다. 그리고 지금 지점을 방문한 적 있는데, 이전의 dp값이 더 작다면 더 갈 필요가 없으니 return 한다.

 

bottom-up 방식으로 풀어져가는 dp문제다.

난 dp가 매우 약하다. dp를 더 많이 풀어봐야겠다. 그리고 문제 분류상은 dfs가 아니라 bfs로 되어있던데 대체 얼캐했지 ;;

#include <iostream>
#include <limits.h>
using namespace std;

int answer = INT_MAX;
int DP[61][61][61];
int DP2[61][61];
int DP3[61];
void dfs(int scv1, int scv2, int scv3, int cnt) {
	if (scv1 <= 0 && scv2 <= 0 && scv3 <= 0) {
		answer = min(answer, cnt);
		return;
	}

	if (scv1 < 0) scv1 = 0;
	if (scv2 < 0) scv2 = 0;
	if (scv3 < 0) scv3 = 0;

	if (DP[scv1][scv2][scv3] <= cnt && cnt != 0) return;
	else DP[scv1][scv2][scv3] = cnt;

	dfs(scv1 - 9, scv2 - 3, scv3 - 1, cnt + 1);
	dfs(scv1 - 9, scv2 - 1, scv3 - 3, cnt + 1);
	dfs(scv1 - 3, scv2 - 9, scv3 - 1, cnt + 1);
	dfs(scv1 - 3, scv2 - 1, scv3 - 9, cnt + 1);
	dfs(scv1 - 1, scv2 - 9, scv3 - 3, cnt + 1);
	dfs(scv1 - 1, scv2 - 3, scv3 - 9, cnt + 1);

}
void dfs(int scv1, int scv2, int cnt) {
	if (scv1 <= 0 && scv2 <= 0) {
		answer = min(answer, cnt);
		return;
	}

	if (scv1 < 0) scv1 = 0;
	if (scv2 < 0) scv2 = 0;
	
	if (DP2[scv1][scv2] <= cnt && cnt != 0) return;
	else DP2[scv1][scv2] = cnt;

	dfs(scv1 - 9, scv2 - 3, cnt + 1);
	dfs(scv1 - 3, scv2 - 9, cnt + 1);
}

void dfs(int scv, int cnt) {
	if (scv <= 0) {
		answer = min(answer, cnt);
		return;
	}

	if (scv < 0) scv = 0;

	if (DP3[scv] <= cnt && cnt != 0) return;
	else DP3[scv] = cnt;

	dfs(scv - 9, cnt + 1);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	int N;
	cin >> N;
	int scv[3];
	for (int i = 0; i < N; i++) 
		cin >> scv[i];
	
	if (N == 3) {
		for (int i = 0; i < scv[0]; i++) {
			for (int j = 0; j < scv[1]; j++) {
				for (int k = 0; k < scv[2]; k++) {
					DP[i][j][k] = INT_MAX;
				}
			}
		}

		dfs(scv[0], scv[1], scv[2], 0);
	}
	else if (N == 2) {
		for (int i = 0; i < scv[0]; i++) {
			for (int j = 0; j < scv[1]; j++) {
				DP2[i][j] = INT_MAX;
			}
		}
		dfs(scv[0], scv[1], 0);
	}
	else {
		for (int i = 0; i < scv[0]; i++) {
				DP3[i] = INT_MAX;
		}
		dfs(scv[0], 0);
	}
	cout << answer;
}