백준 12869 C++

백준 12869

중요한 점은, 공격 횟수의 최솟값을 찾아야 한다는 점이다.

따라서 수많은 시뮬레이션(DFS)를 거쳐서 그 중에서 가장 적은 값을 찾아야만 한다. 코드를 보면 알겠지만, 뮤탈이 데미지를 넣을 수 있는 모든 경우의 수를 dfs로 구했다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;
int N;
int dp[61][61][61];
int scv[3] = { 0, };

int dfs(int x, int y, int z) {
	
	if (x < 0) return dfs(0, y, z);
	if (y < 0) return dfs(x, 0, z);
	if (z < 0) return dfs(x, y, 0);

	if (x == 0 && y == 0 && z == 0) return 0;

	int& res = dp[x][y][z];

	if (res != -1) return res;

	res = 987654321;
	res = min(res, dfs(x - 9, y - 3, z - 1) + 1);
	res = min(res, dfs(x - 9, y - 1, z - 3) + 1);
	res = min(res, dfs(x - 3, y - 9, z - 1) + 1);
	res = min(res, dfs(x - 3, y - 1, z - 9) + 1);
	res = min(res, dfs(x - 1, y - 3, z - 9) + 1);
	res = min(res, dfs(x - 1, y - 9, z - 3) + 1);

	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int y = 0; y < N; y++) {
		cin >> scv[y];
	}

	cout << dfs(scv[0], scv[1], scv[2]) << "\n";



	return 0;
}

BOJ 카테고리 내 다른 글 보러가기