[BOJ/C++] 백준 9655번: 돌 게임

 

 🔗 문제 링크 : https://www.acmicpc.net/problem/9655 

 

---

 

문제

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

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

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

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 #1 | 랜덤 값을 이용한 풀이 (시뮬레이션)

게임 진행에 대한 시뮬레이션을 하듯 1과 3 중 하나를 선택하는 경우를 바탕으로 풀었다.

#include <string>
#include <random>
#include <iostream>
using namespace std;

int main() {
    //.# 랜덤 엔진 초기화
    std::random_device rd;  // 하드웨어 랜덤 숫자 생성 장치를 초기화
    std::mt19937 gen(rd()); // rd를 시드로 사용하여 초기화

    //.# 분산기 설정 (1과 3 중 하나를 선택)
    std::uniform_int_distribution<> dis(0, 1);

    string winner = "";
    int count = 0;
    int n = 0;

    cin >> n;

    while(n != 0) {
        int getStone;
        count++;

        if (n <= 2) {
            getStone = 1;
        }
        else {
            //.# 1 or 3 랜덤 값 생성
            getStone = (dis(gen) == 0) ? 1 : 3;
        }

        n -= getStone;
    }

    winner = count & 1 ? "SK" : "CY";
    cout << winner;

    return 0;
}

 

 

풀이 #2 | Dynamic Programming 을 이용한 풀이

문제를 그대로 코드로 표현한 풀이법 말고, 이 문제의 결과 값에는 규칙이 있었다.

1과 3만 선택할 수 있다는 조건을 따르게 되면, 입력 값이 홀수일 경우에는 무조건 게임을 처음 시작한 "상근"이가 승리한다. 반대로 입력 값이 짝수일 경우에는 나중에 시작한 "창영"이가 승리하게 된다.

 

예를 들어, 입력 값이 홀수인 7이라면,

• 3 -> 3 -> 1
  • 👑 3번째 사람 승리 (=홀수 번째로 게임을 하는 사람 승리)
• 3 -> 1 -> 1 -> 1 -> 1  
  • 👑 5번째 사람 승리 (= 홀수 번째로 게임을 하는 사람 승리)
• 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1
  • 👑 7번째 사람 승리 (= 홀수 번째로 게임을 하는 사람 승리)

어떤 홀수 값을 예로 들어도, 어떤 경우의 수든 결과는 "홀수 번째로 게임을 하는 사람이 승리"한다.

 

 

반대로, 입력 값이 짝수인 8이라면,

• 1 -> 3 -> 1 ->  3
  • 👑 4번째 사람 승리 (=짝수 번째로 게임을 하는 사람 승리)

이 경우에도 어떤 짝수 값을 예로 들어도, 어떤 경우의 수든 결과는 "짝수 번째로 게임을 하는 사람이 승리"한다.

 

이 규칙을 DP로 구현한 문제 풀이는 다음과 같다.

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

bool dp[1001];

int main() {
    int n;
    cin >> n;

    dp[1] = true;
    dp[2] = false;
    dp[3] = true;

    for(int i = 4; i < n + 1; ++i) {
        dp[i] = !dp[i - 3];
    }

    if (dp[n]) {
        cout << "SK";
    }
    else {
        cout << "CY";
    }
    
    return 0;
}

 

---