[백준 12869] - 뮤탈리스크(C++)[골드4]

📕문제

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

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

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

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

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

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

📗입력

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

📗출력

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

 

🔎문제 풀이

• 배열의 크기가 크지않아서 메모리제한은 신경안쓰고 최대한 시간제한만 신경써서 문제를 풀었다.
• 삼차원 배열을 이용해서 1차원 : scv1 , 2차원 : scv2 , 3차원 : scv3
  Graph[x][y][z] = 공격횟수를 저장했다. -> 여기서 공격횟수는 항상 최소값만이 들어간다.
• dfs방식을 이용해서 풀었다.  -> 쭉쭉 방문하다가 체력이 0 0 0 되면 그때의 깊이를 return해줌.
• 항상 방문했던 지역은 깊이를 넣어줌.
• 만약 쭉쭉 탐색하다가, 이미 방문했던 지역이고, 그 때의 값이 현재 깊이보다 작다면 더 방문할 가치가 없음.

 

💻코드

/*
뮤탈리스크 골드4
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;
int n;
vector<vector<vector<int>>> graph;
void attack(int one, int two, int three, int depth);
int ans = INT_MAX;
int main()
{
    cin >> n;
    int scv[n]={0,0,0};
    graph.resize(61, vector<vector<int>>(61, vector<int>(61, 0)));
    for (int i = 0; i < n; i++)
    {
        cin >> scv[i];
    }    
    attack(scv[0],scv[1],scv[2],0);
    cout<<ans;
}
void attack(int one, int two, int three, int depth) // 9-> 3- > 1 차례대로 때려야함.
{        
    if (one <= 0 && two <= 0 && three<=0)
    {
        if (ans > depth) //최소값을 계속해서 넣어줌.
        {
            ans = depth;
            return;
        }
    }
    if(one <0) one =0;
    if(two<0 ) two=0;
    if(three<0) three=0;
    //여기 종료조건.
    if (graph[one][two][three] <= depth && graph[one][two][three] != 0) return;
    //이미 한번 방문했는데 그 때의 저장된 깊이보다 큰 깊이로 연산이 들어온다면 그때는 무시해도 됨.    

    graph[one][two][three]=depth; //그 때 방문했던 경우의 수를 현재의 깊이로 넣어줌.

    if (n == 1) //scv가 하나일때
    {
        attack(one - 9, two, three, depth + 1); // scv가 하나라면 하나의 공격만.
    }
    if (n == 2) //scv가 두개일때
    {
        attack(one - 9, two - 3, three, depth + 1);
        attack(one - 3, two - 9, three, depth + 1);
    }
    if (n == 3) //scv가 세개일때
    {
        attack(one - 9, two - 3, three - 1, depth + 1);
        attack(one - 9, two - 1, three - 3, depth + 1);
        attack(one - 3, two - 9, three - 1, depth + 1);
        attack(one - 3, two - 1, three - 9, depth + 1);
        attack(one - 1, two - 9, three - 3, depth + 1);
        attack(one - 1, two - 3, three - 9, depth + 1);
    }
}

 

✔느낀 점

• 처음에 문제를 제대로 안 읽고, 9 -> 3 -> 1로 순서대로 때려야 하는데 그걸 생각 못해서 많이 헤맸다.
• DP문제는 똑똑하게 풀고 싶어도 잘 안된다...
• 손으로 풀어보는 게 제일 현명한 방법임!