백준 9657번 [돌 게임 3](C++) -yes6686- 티스토리

백준 문제 풀이: 9657 (돌 게임 3)

---

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

문제 설명:

돌 게임 3은 상근이와 창영이가 번갈아가며 게임을 진행하는 게임입니다. 한 번의 턴에서 돌을 1개, 3개, 혹은 4개 가져갈 수 있습니다. 마지막 돌을 가져가는 사람이 승리하며, 시작하는 사람이 이길 수 있는지 확인합니다. - "SK"는 상근이가 승리, "CY"는 창영이가 승리입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int dp[1001]; // dp[i]: 돌이 i개 남았을 때 승리하는 사람 (1: SK, 2: CY)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    dp[1] = 1; // 돌 1개: SK 승리
    dp[2] = 2; // 돌 2개: CY 승리
    dp[3] = 1; // 돌 3개: SK 승리
    dp[4] = 1; // 돌 4개: SK 승리

    // DP 배열 채우기
    for (int i = 5; i <= n; i++) {
        if (dp[i - 1] == 1 && dp[i - 3] == 1 && dp[i - 4] == 1) {
            dp[i] = 2; // SK가 돌을 가져가도 CY가 이길 수 있는 경우
        } else {
            dp[i] = 1; // SK가 돌을 가져가서 SK가 이길 수 있는 경우
        }
    }

    // 결과 출력
    if (dp[n] == 1) {
        cout << "SK";
    } else {
        cout << "CY";
    }
}

---

코드 설명

• 초기값 설정: - 돌이 1개일 때: SK가 가져가 승리 - 돌이 2개일 때: CY가 마지막 돌을 가져가 승리 - 돌이 3개, 4개일 때: SK가 모두 가져가 승리
• DP 배열 채우기: - dp[i - 1], dp[i - 3], dp[i - 4]가 모두 SK가 승리하는 경우라면, CY가 승리합니다. - 반대로, dp[i - 1], dp[i - 3], dp[i - 4] 중 하나라도 CY가 승리한다면, SK가 이길 수 있습니다.

---

시간 복잡도 분석

• DP 배열을 1부터 n까지 채우므로 시간 복잡도는 O(n)입니다.

---

입출력 예시

• 입력 예시:

  6

• 출력 예시:

  CY

• 설명: 돌이 6개일 때, SK가 돌을 가져가면 CY가 이길 수 있는 선택을 할 수 있습니다.

---

결론

이 문제는 동적 프로그래밍(DP)을 이용해 각 돌의 개수에서 누가 이길 수 있는지 판단하는 문제입니다. 각 단계에서 상대방의 승패를 이용해 현재 상황에서의 승자를 결정하는 방식으로 효율적으로 해결할 수 있습니다.