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

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

---

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

문제 설명:

돌 게임은 돌을 1개 또는 3개 가져갈 수 있는 게임입니다. 두 사람이 번갈아가며 게임을 진행하며, 마지막 돌을 가져가는 사람이 승리합니다. 주어진 돌의 개수 n에 대해, 시작하는 사람이 이길 수 있는지 확인하여 이긴 사람을 출력합니다. - "SK"는 상근이가 승리, "CY"는 창영이가 승리입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

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

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

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

    // 결과 출력
    dp[n] == 1 ? cout << "SK" : cout << "CY";
}

---

코드 설명

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

---

시간 복잡도 분석

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

---

입출력 예시

• 입력 예시:

  4

• 출력 예시:

  CY

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

---

결론

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