[백준] 9655번: 돌 게임 | C++ 풀이

# 문제

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

이미지를 클릭하면 백준 문제 페이지로 이동합니다.

 

 

---

 

# 풀이1

간만에 돌아온 알고리즘 풀이

해당 문제는 아주 간단하게 풀 수도 있지만 다이나믹 프로그래밍 DP로도 풀어볼 수 있다. 약간 DP 맛보기 문제랄까?

 

우선 아주 간단하게 푸는 방법 먼저 확인해보자.

#include <iostream>
using namespace std;

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

 

정말 간단하다! 몇 개의 입력 n을 가정해두고 누가 이기는지 직접 적어보자.

 

n	게임	승자
1	상근(1)	SK
2	상근(1) - 창영(1)	CY
3	1. 상근(3) 2. 상근(1) - 창영(1) - 상근(1)	SK
4	1. 상근(3) - 창영(1) 2. 상근(1) - 창영(3) 3. 상근(1) - 창영(1) - 상근(1) - 창영(1)	CY
5	1. 상근(3) - 창영(1) - 상근(1) 2. 상근(1) - 창영(1) - 상근(3) 3. 상근(1) - 창영(1) - 상근(1) - 창영(1) - 상근(1)	SK

 

직접 적어가며 몇 가지 입력을 확인하다보면, 게임이 어떻게 흘러가든 입력 n에 따른 승자는 항상 동일한 것을 확인할 수 있다.

따라서 우리는 입력 n과 승자의 관계를 알아내면 된다는 뜻!

 

이 문제는 아주 간단하게 해결되는데 입력 n이 홀수인 경우에는 항상 상근이가 승리하고,

입력 n이 짝수인 경우에는 항상 창영이가 승리한다.

 

코드로 짜는 것은 아주 간단하니 바로 DP를 활용해 푸는 방법을 알아보자.

 

 

---

 

 

# 풀이2

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

int main(){
    int n;
    cin >> n;
    
    const int MAX = 1001;
    int D[MAX]; // DP 테이블 생성 및 초기값 할당
    D[1] = 1;
    D[2] = 2;
    D[3] = 1;

    for(int i = 4; i <= n; i++){
        D[i] = min(D[i-1] + 1, D[i-3] + 1);
    }

    if(D[n]%2 == 0) cout << "CY";
    else cout << "SK";
    
    return 0;
}

 

DP로 문제를 풀 땐 해당 문제가 작은 문제들로 나누어지는지, 그 작은 문제들이 반복되어 나타나고/사용되고 있는지를 먼저 확인해야 한다.

현재 풀고 있는 문제에서는 1 과 3중 어떤 것을 선택하는지의 문제로 나누어지고, 이것을 활용해 승리까지 몇 턴이 도는가를 DP 테이블에 저장해 반복적으로 활용하면 원하는 최종 정답을 구해낼 수 있다는 것을 기억하고 코드를 살펴보자.

 

const int MAX = 1001;
int D[MAX]; // DP 테이블 생성 및 초기값 할당
D[1] = 1;
D[2] = 2;
D[3] = 1;

 

입력 N의 범위가 1 ≤ N ≤ 1000 이므로 최대 1001의 값을 갖는 DP 테이블을 생성해주었다. (여기선 배열의 형태지만 편의상 DP 테이블로 언급) 그리고 간단하게 구할 수 있는, 작은 문제들을 해결해 초기값으로 할당해준다. 이때 턴이 최소한으로 돌아가는 것을 문제에서 언급한 완벽한 게임이라고 가정하였다. (따라서 D[3] = 1)

 

 

이제 작은 문제들로 큰 문제를 해결해보자.

 

입력이 4인 경우 우리는 1, 혹은 3을 선택할 수 있다.

따라서 D[3]에서 1을 선택하는 턴을 하나 더해주고, D[1]에서 3을 선택하는 턴을 하나 더해주는 두 개의 선택지가 존재한다.

또한 완벽한 게임을 가정했으므로 두 가지 선택지 중 더 적은 턴을 사용하는 것을 D[4]로 정의해줄 수 있다.

 

for(int i = 4; i <= n; i++){
    D[i] = min(D[i-1] + 1, D[i-3] + 1);
}

 

위에서 말로 풀어 확인해본 과정을 일반화해보면 위와 같은 코드를 얻을 수 있고, 

해당 과정을 통해 구해준 최소한의 D[i]로 홀수, 짝수를 따지면(첫번째 풀이와 동일하게) 누가 승리했는지 찾을 수 있다.

 

 

---

 

 

(아래) 풀이 1 / (위) 풀이 2

 

 

---

 

 

 

9655번: 돌 게임