문제

문제 링크

해설

• 쉬운듯 보이면서도 막상 풀기 시작하면 고려할게 참 많은 문제입니다.
  • 중간에 사망하는 몬스터가 생기면 몬스터 수가 줄어들고
  • 몬스터 수가 바뀌면 고려해야 하는 데미지 조합과 조합 개수가 바뀌며
  • 무엇보다 체력이 최대 60밖에 안 되지만, 최악의 경우에 호출되는 콜스택 횟수가 너무 많습니다.
• 맞습니다. DP로 풀어야 하는 문제입니다.
  • 이전에 어떤 데미지를 입었건 간에, 체력 x에 도달한 몬스터는 다음번에 9, 3, 1 중 하나의 데미지를 입을 것이기 때문입니다.
  • 즉, 부분문제의 형태가 바뀌지 않으며, 이전 계산한 결과를 그대로 사용할 수 있기 때문에 이 문제는 DP로 풀 수 있습니다.
• dp[61][61][61] 3차원 배열을 만들고 dp[x][y][z]를 체력 x, y, z를 가진 세 마리의 SCV를 죽일 수 있는 최소 공격횟수로 정의합시다.
• 배열 전체를 1e9와 같은 높은 값으로 초기화한 뒤 9, 3, 1 세 가지 숫자로 만들 수 있는 6가지 조합에 대한 재귀함수를 돌립니다. ({9, 3, 1}, {9, 1, 3}, {3, 9, 1}, {3, 1, 9}, {1, 9, 3}, {1, 3, 9})

코드

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

constexpr int dmg[3] = {9, 3, 1};
int N, dp[61][61][61];

int attack(int scv1, int scv2, int scv3) {
    if (scv1 == 0 && scv2 == 0 && scv3 == 0) return 0;
    if (dp[scv1][scv2][scv3] != 1e9) return dp[scv1][scv2][scv3];

    int comb[3] = {0, 1, 2};
    int& ret = dp[scv1][scv2][scv3];
    do {
        ret = min(ret, attack((max(0, scv1 - dmg[comb[0]])),
                              (max(0, scv2 - dmg[comb[1]])),
                              (max(0, scv3 - dmg[comb[2]]))) + 1);
    } while(next_permutation(comb, comb + 3));
    return ret;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> N;
    
    int scv[3] = {0, 0, 0};
    for (int i = 0; i < N; i++) cin >> scv[i];
    fill(&dp[0][0][0], &dp[0][0][0] + (61 * 61 * 61), 1e9);
    
    cout << attack(scv[0], scv[1], scv[2]) << '\n';
    
    return 0;
}

소스코드 링크

결과