백준12869 뮤탈리스크

작성일 | In

문제 링크

  • http://icpc.me/12869

사용 알고리즘

  • DP

풀이

dp[x][y][z] = 첫 번째 scv의 체력이 x, 두 번째 scv의 체력이 y, 세 번째 scv의 체력이 z일 때의 정답 으로 정의합시다.
N이 1이나 2일때는 남는 자리에 0을 넣으면 됩니다.

약간의 상수커팅을 위해 x, y, z를 오름차순으로 유지시켰습니다.

상태공간의 개수는 603개, 각 상태마다 O(1)에 해를 구하므로 충분히 시간 내에 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int dp[66][66][66];

int f(int a, int b, int c){
	if(a <= 0 && b <= 0 && c <= 0) return 0;
	int &res = dp[a][b][c];
	if(res != -1) return res;
	int arr[3] = {1, 3, 9};

	int ans = 1e9+7;
	do{
		int x = a - arr[0]; x = max(x, 0);
		int y = b - arr[1]; y = max(y, 0);
		int z = c - arr[2]; z = max(z, 0);
		if(x > y) swap(x, y);
		if(x > z) swap(x, z);
		if(y > z) swap(y, z);
		ans = min(ans, f(x, y, z)+1);
	}while(next_permutation(arr, arr+3));
	return res = ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	memset(dp, -1, sizeof dp);
	if(n == 1){
		int t; cin >> t;
		cout << f(0, 0, t);
	}else if(n == 2){
		int a, b; cin >> a >> b;
		if(a > b) swap(a, b);
		cout << f(0, a, b);
	}else{
		int a, b, c; cin >> a >> b >> c;
		if(a > b) swap(a, b);
		if(a > c) swap(a, c);
		if(b > c) swap(b, c);
		cout << f(a, b, c);
	}
}