[백준] 9655 돌 게임(C++)

 

문제 URL:

9655번: 돌 게임 (acmicpc.net)

9655번: 돌 게임

탁자 위에 N개의  돌이 있고 상근이와 창영이가 번갈아가면서 돌을 가져간다. 돌을 1개 또는 3개 가져갈 수 있다고 할 때, 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 상근이의 차례가 선으로 두 사람이 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하자.

 

게임에서 돌을 1개 또는 3개만 가져갈 수 있으므로 처음에 주어진 n이 홀수라면 상근이가 이기게 되며, 짝수라면 창영이가 이기게 된다. 이에 따른 코드는 아래 <코드 1>과 같다. 

 

이 문제는 다이나믹 프로그래밍을 이용하여 풀 수도 있었다. 게임에서 두 사람이 번갈아가며 돌을 홀수개로(1개 또는 3개) 가져가기 때문에 상근이는 홀수번째 차례에서만 이기며, 창영이는 짝수번째 차례에서만 이기게 된다.

따라서 돌의 개수가 n일 때의 게임 횟수를 구하여 홀짝을 알아보면 된다. 돌을 1개나 3개만 가져갈 수 있으므로 n번째 차례에서의 게임 횟수는 이전 dp[n-1]에 1을 더한 값 또는 dp[n-3]에 1을 더한 값이 된다. 이 중 더 작은 값을 결국 dp[n]에 할당해 주면 된다. 

dp[n] = min(dp[n-1] + 1, dp[n-3] + 1)

이 원리를 토대로 코드를 작성하면 아래의 <코드 2>와 같다. 

---

<코드 1>

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    if(n%2 == 0)
        cout << "CY";
    else
        cout << "SK";
    return 0;
}

 

<코드 2>

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

int n;
int dp[1001];

int main(){
    cin >> n;
    
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 1;
    for(int i = 4; i<= n; i++)
        dp[i] = min(dp[i-1] + 1, dp[i-3] + 1);
    
    if(dp[n]%2 == 0)
        cout << "CY";
    else
        cout << "SK";
    return 0;
}

출처: [C++] 백준 9655번 돌 게임 (tistory.com)