[99클럽/코딩테스트 챌린지/C++] 돌 게임 문제 해결 및 최적화 접근법

문제 링크:

https://www.acmicpc.net/problem/9655

 

📝 문제 요약

• 두 명의 플레이어가 번갈아가며 돌을 가져가는 게임입니다.
• 돌은 한 번에 1개 또는 3개씩 가져갈 수 있으며, 마지막 돌을 가져가는 사람이 승리합니다.
• 상근이가 먼저 시작하며, 두 플레이어는 항상 최적의 전략으로 게임을 진행합니다.
• 입력으로 주어진 돌의 개수 N(1 ≤ N ≤ 1000)에 따라 승자를 구합니다.

📌 접근법

1, 게임의 성질 파악:

• 현재 돌의 개수 i에서 돌을 가져가면 남은 돌의 개수는 i - 1 또는 i - 3입니다.
• 상대가 남은 돌의 개수로 패배하는 경우라면 현재 플레이어가 승리합니다.

2, DP (동적 계획법) 사용:

• dp[i]: 돌이 i개 남았을 때 이기는 사람을 나타냄.
  • true: 상근이(SK)가 이김.
  • false: 창영이(CY)가 이김.
• 점화식:
  dp[i] = !dp[i - 1] || !dp[i - 3]
  • 남은 돌의 개수가 i - 1 또는 i - 3일 때 상대가 지는 경우가 있다면, 현재 플레이어가 승리.

3, 초기값 설정:

• dp[1] = true: 돌이 1개일 때 상근이가 가져가서 승리.
• dp[3] = true: 돌이 3개일 때 상근이가 가져가서 승리.
• 나머지는 점화식을 통해 계산.

📌 코드 구현

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

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

    // DP 테이블 초기화
    vector<bool> dp(N + 1, false);

    // 초기값 설정
    dp[1] = true; // 돌 1개일 때 SK 승리
    if (N >= 3) dp[3] = true; // 돌 3개일 때 SK 승리

    // DP 점화식 계산
    for (int i = 4; i <= N; i++) {
        dp[i] = !dp[i - 1] || !dp[i - 3];
    }

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

    return 0;
}

📌 코드 설명

1, DP 배열 정의:

• vector<bool> dp: 돌의 개수 N에 따라 각 상황에서 승자를 기록합니다.

2, 점화식 계산:

• dp[i]: 현재 돌 개수에서 SK가 이길 수 있는지 여부를 기록.
• 남은 돌이 i - 1 또는 i - 3에서 CY가 이기지 못하는 경우라면 SK가 이깁니다.

3, 결과 출력:

• dp[N] 값에 따라 SK 또는 CY를 출력.

📌 배운 점

1, 동적 계획법(DP)의 적용:

• 게임에서 최적의 전략을 적용할 때, 현재 상태와 다음 상태 간의 관계를 점화식으로 나타낼 수 있다는 점을 배웠습니다.
• 이전 상태를 기반으로 결과를 계산하여 중복된 연산을 줄일 수 있습니다.

2, 문제 단순화:

• 모든 경우를 계산하거나 저장하는 대신, 게임의 승패를 판단하는 규칙(점화식)을 파악해 효율적으로 문제를 해결할 수 있었습니다.

3, 최적화와 메모리 사용:

• DP 배열을 N + 1 크기로 설정하여, 필요한 최소한의 메모리만 사용.
• 각 상태는 이전 두 상태만 참조하므로, 메모리를 더욱 최적화할 여지가 있음을 확인했습니다.

📌 느낀 점

• 이번 문제를 통해 동적 계획법을 게임 이론에 적용하는 방법을 익혔습니다. 점화식을 설정하는 과정에서 현재 상태와 다음 상태의 관계를 이해하는 것이 중요하다는 것을 배웠습니다.
• 단순히 결과를 맞히는 코드를 작성하는 것에서 벗어나, 최적의 방법을 찾아 효율적으로 문제를 해결하는 과정이 흥미로웠습니다.
• 앞으로는 메모리와 시간 복잡도를 더욱 줄이는 최적화 방법도 고려해야겠다고 느꼈습니다.