[BOJ/C++] 백준 12869 - 뮤탈리스크

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

12869번: 뮤탈리스크

풀이 과정

scv는 최대 3개가 있을 수 있고, scv의 체력은 최대 60이다. 따라서 각 scv의 체력의 조합은 61의 3승이다. 약 20만의 경우의 수가 있으므로, 전부 탐색해도 큰 문제가 없이 풀 수 있다. 

D[a][b][c] = 체력의 조합이 (a, b, c) 일 때 모두 파괴하는 최소 공격 횟수

총 세 가지 SCV에 대해서 체력을 감소시킬 때는 3!의 경우의 수가 있으므로, 아래와 같이 점화식을 세울 수 있다. 

D[a][b][c] = min ( D[a - 9][b - 3][c - 1],
                   D[a - 9][b - 1][c - 3], 
                    D[a - 3][b - 9][c - 1],
                    D[a - 3][b - 1][c - 9],
                    D[a - 1][b - 3][c - 9],
                    D[a - 1][b - 9][c - 3]) + 1;

1을 더해주는 이유는, 각 공격에 대해서 최소 횟수를 구하고 있으므로 공격의 총 횟수를 재귀적으로 얻기 위함이다.

 

아래의 코드에서는 아래 두 경우를 고려해서 조금 코드를 다르게 작성하였다. 

 

(1) 배열이 음수가 되는 경우를 보완하기 위한 배열 크기 증가

 최대 60 0 0 이라고 했을 때, 60의 체력을 음수로 만들기 위해 1이 60번 곱해질 수 있다. 이 경우 다른 svc의 체력은 최소 60 * 9  = 540만큼 음수로 떨어질 수 있으므로 기존 값에 540을 더해서 연산을 해주었고, 이에 따라 배열에 들어갈 수 있는 값은 최소 0 이상 최대 600 이하의 숫자가 된다. 따라서 DP 배열의 크기를 600으로 설정해준다.

(2) scv의 체력 대신 연산 횟수를 배열에 넣기

D[a][b][c] 로 설명한 것과는 다르게 D[a][b][i] = svc의 체력이 각각 a, b이고 공격한 횟수가 i일 때 공격 횟수의 최소 횟수로 지정하였다. 이유는 (1) 에서 배열의 크기를 늘림에 따라 메모리를 많이 차지하게 되어 오류가 발생할 수 있기 때문에 배열의 크기를 줄이기 위함이다. 공격한 횟수 i를 알면 c = sum - (13 * i) - (a + b) 공식에 의해 c를 알 수 있으므로 이렇게 문제를 설계하였다.

소스 코드

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

int dp3[601][601][61];
int dp2[601][61];
int dp1[601];
int scv[3];

int sum;
int solve(int a, int b, int i) {
	int c = sum - (13 * i) - (a - 540 + b - 540);
	if (a <= 540 && b <= 540 && c <= 0) return 0;

	int& ret = dp3[a][b][i];
	if (ret != -1) return ret;

	vector<int> candidates;
	candidates.push_back(solve(a - 9, b - 3, i + 1) + 1);
	candidates.push_back(solve(a - 9, b - 1, i + 1) + 1);
	candidates.push_back(solve(a - 3, b - 9, i + 1) + 1);
	candidates.push_back(solve(a - 3, b - 1, i + 1) + 1);
	candidates.push_back(solve(a - 1, b - 9, i + 1) + 1);
	candidates.push_back(solve(a - 1, b - 3, i + 1) + 1);
	sort(candidates.begin(), candidates.end());
	return ret = candidates[0];
}

int solve(int a, int i) {
	int b = sum - (12 * i) - (a - 540);
	if (a <= 540 && b <= 0) return 0;
	int& ret = dp2[a][i];
	if (ret != -1) return ret;

	vector<int> candidates;
	candidates.push_back(solve(a - 9, i + 1) + 1);
	candidates.push_back(solve(a - 3, i + 1) + 1);
	sort(candidates.begin(), candidates.end());
	return dp2[a][i] = candidates[0];
}

int solve(int a) {
	if (a <= 540) return 0;
	int& ret = dp1[a];
	if (ret != -1) return ret;

	vector<int> candidates;
	candidates.push_back(solve(a - 9) + 1);
	return dp1[a] = candidates[0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);

	memset(dp1, -1, sizeof(dp1));
	memset(dp2, -1, sizeof(dp2));
	memset(dp3, -1, sizeof(dp3));
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> scv[i];

	if (n == 1)
		cout << solve(scv[0] + 540) << endl;
	else if (n == 2) {
		sum = scv[0] + scv[1];
		cout << solve(scv[0] + 540, 0) << endl;
	}
	else {
		sum = scv[0] + scv[1] + scv[2];
		cout << solve(scv[0] + 540, scv[1] + 540, 0) << endl;
	}
	return 0;
}

 

 

조금 더 멋진 풀이를 보자

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

int dp[61][61][61]; 

int solve(int a, int b, int c) {
	if (a < 0) return solve(0, b, c); 
	if (b < 0) return solve(a, 0, c); 
	if (c < 0) return solve(a, b, 0); 
	if (a == 0 && b == 0 && c == 0) return 0; 

	int& ret = dp[a][b][c]; 
	if (ret != -1) return ret;

	vector<int> p = { 1,3, 9 }; 
	do {
		int cand = solve(a - p[0], b - p[1], c - p[2]); 
		if (ret == -1 || ret > cand) ret = cand; 

	} while (next_permutation(p.begin(), p.end())); 
	ret++; 
	return ret; 
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);

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

	cout << solve(scv[0], scv[1], scv[2]) << endl;

	return 0;
}

내가 만든 코드는 함수가 여러 개이고, 재귀호출하는 부분의 가독성이 어렵다는 문제가 있었다. 또한 음수값의 입력을 피하기 위해 540을 더해주는 바람에 코드를 작성하는 과정에서 실수할 수 있는 부분이 많았다.

조금 더 깔끔한 코드를 만들기 위해 다른 코드를 참고하였는데,  dp 배열과 함수를 일반화하고, 음수 값을 넣지 않기 위해 음수 입력값에 대해 모두 0으로 넘어가게 하였다. 

SVC가 몇 개든, 0이기만 하면 그 SVC는 더 이상 신경 쓸 대상이 아니다. 따라서 처음에 SVC의 체력을 모두 0으로 세팅하고, 입력을 받아 실제로 존재하지 않는 SVC의 경우 0으로 체력이 함수의 입력값으로 들어가게 한다.

 

또한 <algorithm> 헤더의 next_permutation 함수를 사용해 1, 3, 9를 체력에서 빼는 6가지 경우를 모두 탐색한다. 만약 svc가 2개라면 9, 3 만 빼야하는데 1은 왜 빼냐고 할 수 있는데, 항상 9 -> 3 -> 1 순으로 빠지기 때문에 svc a, b는 1이 빠지는 것보다 항상 최솟값만큼 빠지게 되는 특징이 있다. 그렇기 때문에 svc의 체력에서 1이 빠지게 되는 오류가 생기더라도 최소값이 되지는 못하므로, 결괏값이 보장이 되는 것이다. 

 

이러한 통찰력은 어디서 나오는 건지 신기할 따름이다 ,, 👍🧐