[Gold / 12869] 뮤탈리스크

문제 링크

---

🔷 분류

다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색

✒️ 문제 설명

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

첫 번째로 공격받는 SCV는 체력 9를 잃는다.
두 번째로 공격받는 SCV는 체력 3을 잃는다.
세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

⬅️ 입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

➡️ 출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

💻 코드 (C++)

#include <iostream>
#include <queue>
#include <utility>
#include <limits.h>
#include <algorithm>
#define INF 99999
using namespace std;

int n;
int a, b, c;
int hp[61][61][61];
int dx[3] = {1, 3, 9};

int dp(int a, int b, int c) {
	if (a == 0 && b == 0 && c == 0) return 0;
	if (hp[a][b][c] != 0) return hp[a][b][c];
	
	hp[a][b][c] = INF;
	
	do { // 6 가지 경우의 수에 대해 DP 
    int na, nb, nc;
		na = max(0, a-dx[0]);
		nb = max(0, b-dx[1]);
		nc = max(0, c-dx[2]);
		hp[a][b][c] = min(hp[a][b][c], dp(na, nb, nc) + 1);
	} while (next_permutation(dx, dx+3)); // permutation 만들기
    
  return hp[a][b][c];
}
	

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	if (n == 3) {
		cin >> a >> b >> c;
	} else if (n == 2) {
		cin >> a >> b;
	} else
		cin >> a;
	int ans = dp(a, b, c);
	
	cout << ans;
	return 0;
}