[백준] 9657번: 돌 게임 3 풀이 및 해설(C++)

 

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

9657번: 돌 게임 3

 

C++로 작성한 백준 문제 9657번 돌 게임 3에 대한 문제 풀이다.

실버 3 문제로 동적계획법이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

---

문제 파악하기

1. 게임에 있어 현재보다 많은 돌을 가져갈 수는 없다. 즉 2개 남아있는 상황에서 3개나 4개를 가져가고 승리선언 하는건 불가능하다.
2. dp[돌의 수] 배열로 누가 이길지 저장할 수 있다.
3. 만약 이전 턴에서 어떻게 해도 필승이었다면 지금 턴에는 반대로 필패다 

 

 

 

 

 

---

 

코드 및 설명

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define size 10
using namespace std;

int arr[1002];


int whowin(int a){
    if(a<=4){
        return arr[a];
    }
    for(int i=5; i<a+1; i++){
        if (arr[i-1]&&arr[i-3]&&arr[i-4]){
            arr[i]=0;
        }
        else{
            arr[i]=1;
        }
    }
    return arr[a];
    
}

int main()
{
    fastio;
    arr[1]=1;
    arr[2]=0;
    arr[3]=1;
    arr[4]=1;
    int a;
    scanf("%d",&a);
    if(whowin(a)){
        printf("SK");
    }else{
        printf("CY");
    }

	return 0;
}

 

• 남은 돌에 따라 누가이길지 배열을 만들어 저장한다. 그리고 for문을 통해 동적계획법으로 현재 요구된 값들을 처리한다.
• 선공을 기준으로 승패를 저장했다.
• outofbounderror 방지겸, 점화식의 첫항을 만드는 겸 해서 처음 1~4번째만 정해주고, 이후로는 점화식을 활용해서 정했다.
• 만약 이전 턴, 그러니까 돌이 1,3,4개 적었을때의 경우가 모두 선공 기준으로 승리였다면, 이번턴은 무조건 진다. 턴이 반전되었기 때문이다. 반대로 지금보다 돌이 1,3,4 개 적었을때중 한번이라도 진 경우가 있다면 그 경우를 택하면 되기에 승리한다.
• 만약 문제 내에서 한번에 여러개를 물었으면 for문 보다 memoization을 더 적극 활용했겠지만 1번만 물어봐서 그냥 for문 돌렸다. 

 

---

 

헤매었던 부분

• 상식적으로 조건이 선공한테 너무 유리한거 아닌가? 말이되나 싶었다. if문으로 따졌을때 3개 중에 하나라도 False 가 있으면 되는 셈이니. 그런데 그게 맞았다. 마지막을 외쳤을때 이기는 게임은 선공이 시사하는 바가 아주 크다. 사실상 원하는 돌의 개수로 조정하고 들어갈 수 있으니 말이다.

 

 

 

 

 

---

 

마무리

동적계획법 뿐만 아니라 게임이론과 관련된 문제였다.