백준_뮤탈리스크_12869

백준_뮤탈리스크_12869

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

문제

• 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아 있다.
• 각각의 SCV 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수 없다.
• 뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있습니다.
  • 첫 번째로 공격 받는 SCV는 체력 9를 잃는다.
  • 두 번째로 공격 받는 SCV는 체력 3를 잃는다.
  • 세 번째로 공격 받는 SCV는 체력 1를 잃는다.
• SCV의 체력이 0 또는 그 이하가 되버리면, SCV는 그 즉시 파괴한다.
• 한 번의 공격에서 같은 SCV를 여러번 공격할 수는 없다.
• 남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구해라.

어떻게 풀었는가

• 조건

  • n은 1 이상 3 이하이다.
  • SCV는 60 이하의 체력을 가진다.

• 풀이

1. 뮤탈리스크의 공격 조합을 permutation을 사용하여 만든다.

   • 1,3,9 / 1,9,3 / 3,1,9 / 3,9,1 / 9,1,3 / 9,3,1

2. scv의 체력을 vector에 저장한다.

   • 무조건 scv는 3개가 있다고 가정하고 값을 저장한다.
   • 만약 3개보다 작은 경우 나머지는 0으로 값을 초기화한다.

3. getAttackCount 함수를 사용하여 완전 탐색을 한다.

   • scv들의 체력 합이 0인 경우 공격 횟수가 최솟값인지 확인한다.

     • 공격횟수가 최솟값인 경우 attackCount를 최솟값으로 변경한다.
     • 해당 함수를 종료한다.

   • 뮤탈리스크의 공격 조합을 사용하여 scv를 공격한다.

     • 만약 공격한 후 attackCheck배열이 "0" 또는 "공격 횟수 + 1"보다 큰 경우 해당 배열을 "공격 횟수 + 1"을 저장한다.

4. attackCount[0][0][0]을 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int setItems[6][3];
int attackCheck[61][61][61];
int attackCount = INT_MAX;

void makeItems()
{
    vector<int> tempNum = { 1,3,9 };
    int index = 0;
    do
    {
        setItems[index][0] = tempNum[0];
        setItems[index][1] = tempNum[1];
        setItems[index][2] = tempNum[2];
        ++index;
    } while (next_permutation(tempNum.begin(), tempNum.end()));
}

void getAttackCount(vector<int> scv, int count)
{
    int sum = scv[0] + scv[1] + scv[2];
    if (sum == 0)
    {
        attackCount = min(attackCount, count);
        return;
    }

    vector<int> tempV(3);
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            tempV[j] = scv[j] - setItems[i][j] > 0 ? scv[j] - setItems[i][j] : 0;
        }
        if (attackCheck[tempV[0]][tempV[1]][tempV[2]] == 0 || attackCheck[tempV[0]][tempV[1]][tempV[2]] > count + 1)
        {
            attackCheck[tempV[0]][tempV[1]][tempV[2]] = count + 1;
            getAttackCount(tempV, count + 1);
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;

    makeItems();
    vector<int> scv(3);
    for (int i = 0; i < n; ++i)
    {
        cin >> scv[i];
    }
    for (int i = n; i < 3; ++i)
    {
        scv[i] = 0;
    }
    attackCheck[scv[0]][scv[1]][scv[2]] = true;
    getAttackCount(scv, 0);

    cout << attackCheck[0][0][0] << '\n';
    return 0;
}

결과