12869번: 뮤탈리스크 [C++]

뮤탈리스크

 

시간 제한            메모리 제한         제출          정답               맞힌 사람           정답 비율

2 초

512 MB

5528

2655

1972

47.783%

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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 복사

3
12 10 4

예제 출력 1 복사

2

예제 입력 2 복사

3
54 18 6

예제 출력 2 복사

6

예제 입력 3 복사

1
60

예제 출력 3 복사

7

예제 입력 4 복사

3
1 1 1

예제 출력 4 복사

1

예제 입력 5 복사

2
60 40

예제 출력 5 복사

9

힌트

1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.

 

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

12869번: 뮤탈리스크

 

흐름

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;
int a[3],n,visited[64][64][64];

int _a[6][3]={ //공격 경우의 수
    {9,3,1},
    {9,1,3},
    {3,1,9},
    {3,9,1},
    {1,3,9},
    {1,9,3}
};
struct A{ //SCV 체력 저장 자료구조
    int a,b,c;
};
queue<A> q;

//bfs 수행
int solve(int a, int b, int c){
    visited[a][b][c]=1;
    q.push({a,b,c});
    while(q.size()){
        int a=q.front().a;
        int b=q.front().b;
        int c=q.front().c;
        q.pop();
        if(visited[0][0][0]) break; //도착하면 종료
        for(int i=0;i<6;i++){ //공격 6가지 옵션
            int na = max(0, a-_a[i][0]); //최소값 0으로 제한
            int nb = max(0, b-_a[i][1]);
            int nc = max(0, c-_a[i][2]);
            if(visited[na][nb][nc]) continue;
            visited[na][nb][nc]=visited[a][b][c]+1;
            q.push({na,nb,nc});
        }
    }
    return visited[0][0][0]-1; //정답 출력
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++) cin>>a[i];
    //2. 정답 구해서 출력
    cout << solve(a[0],a[1],a[2]) <<"\n"; //초기 체력

    return 0;
}

 

유의할 점

• 최단거리, 최단 횟수를 물어볼때는 bfs를 생각하자.
• 1~3개가 입력된다고 가정할때 파라미터는 최대 개수 기준으로 만들자
• 값을 업데이트하는 옵션이 있을때 for문을 사용하여 그 옵션 개수만큼 반복한다.

for(int i=0;i<6;i++){ //공격 6가지 옵션
            int na = max(0, a-_a[i][0]); //최소값 0으로 제한
            int nb = max(0, b-_a[i][1]);
            int nc = max(0, c-_a[i][2]);
            if(visited[na][nb][nc]) continue;
            visited[na][nb][nc]=visited[a][b][c]+1;
            q.push({na,nb,nc});
        }

• 최소값을 0으로 하려면 위와같이 max 함수를 이용한다.

 

정리한 최종 코드

#include <bits/stdc++.h>
using namespace std;

int n, a[3], visited[64][64][64];
//공격 경우의 수
int attack[6][3]={
    {-9,-3,-1},
    {-9,-1,-3},
    {-3,-9,-1},
    {-3,-1,-9},
    {-1,-9,-3},
    {-1,-3,-9}
};
//체력 저장 자료구조
struct A{
    int a,b,c;
};

queue<A> q;
//bfs 수행
int solve(int a, int b, int c){
    visited[a][b][c]=1;
    q.push({a,b,c});
    while(q.size()){
        int a= q.front().a;
        int b= q.front().b;
        int c= q.front().c;
        q.pop();
        if(visited[0][0][0]) break; //체력 모두 방전되었을때 종료
        for(int i=0;i<6;i++){ //공격 경우의 수
            int na = max(0, a+attack[i][0]);
            int nb = max(0,b+attack[i][1]);
            int nc = max(0,c+attack[i][2]);
            if(visited[na][nb][nc]) continue;
            visited[na][nb][nc]=visited[a][b][c]+1;
            q.push({na,nb,nc});
        }
    }
    return visited[0][0][0]-1;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++) cin >>a[i];
    //2. 정답 구해서 출력하기
    cout << solve(a[0], a[1], a[2])<<"\n";

    return 0;
}