[백준] 9655번: 돌 게임 (Java)

1. 문제설명

돌 게임은 탁자 위에 돌 N개가 있을 때 상근이와 창영이가 턴을 번갈아가면서 돌을 1개 또는 3개 가져가고, 마지막 돌을 가져가는 사람이 이기는 게임이다. 게임은 상근이가 먼저 시작하고, 이기는 사람을 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

REF) https://propercoding.tistory.com/21

• 문제에서 “두 사람이 완벽하게 게임을 했을 때”가 조건이기 때문에 최적의 전략을 사용해야 한다.

N=1: 상근이가 돌 1개를 가져가므로 상근이의 승리
N=2: 상근이가 1개를 가져가면 창영이가 남은 1개를 가져가므로 창영이의 승리
N=3: 상근이가 3개를 가져가므로 상근이의 승리
N=4: 상근이가 1개 또는 3개를 가져가면 창영이가 3개 또는 1개를 가져가므로 창영이의 승리
N=5: 상근이가 1개 또는 3개를 가져갈 수 있다.
→ 1개를 가져간 경우: 4개가 남고 창영이나 1개 또는 3개를 가져가면 3개 또는 1개가 남으므로 상근이의 승리
→ 3개를 가져간 경우: 2개가 남고 창영이가 1개를 가져가면 상근이가 1개를 가져가므로 상근이의 승리

• `dp[i]`에 돌이 `i`개 남았을 때 승패를 결정하는 최소의 차례 수를 저장한다.
• `dp[i] = Math.*min*(dp[i-1], dp[i-3]) + 1`
  • 1개 또는 3개의 돌을 가져갔을 때, 다음 상대방이 이길 수 있는 최소의 차례 수를 계산한다.
  • 최솟값을 선택하여, 상대방에게 최악의 상황을 유도한다.
• `dp[n]`이 홀수이면 상근이의 승리(SK), 짝수이면 창영이의 승리(CY)이다.

 

3. 최종 코드

package lsj.study.algorithm_note.DP;

import java.io.*;

public class BJ_9655 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 돌의 개수
        int[] dp = new int[1001];
        dp[1] = 1; // 1 -> 홀 -> 상근 승리
        dp[2] = 2; // 1+1 => 짝 -> 창영 승리
        dp[3] = 1; // 3 => 홀 -> 상근 승리

        for(int i=4; i<=n; i++) {
            // 돌 1개 또는 3개를 가져갔을 때
            // 남은 돌의 상태에서 최적의 전략을 선택
            dp[i] = Math.min(dp[i-1], dp[i-3]) + 1;
        }

        if(dp[n]%2 == 0) {
            // dp[n]이 짝수이면 창영이의 승리
            System.out.println("CY");
        } // dp[n]이 홀수이면 상근이의 승리
        else System.out.println("SK");
    }
}

 

4. 느낀점 or 기억할정보

DP는 개념적으로는 이해한 것 같은데 막상 문제로 보면 어려운 것 같다. 좀 더 연습이 필요할 것 같다.

문제에서 "완벽하게 게임을 했을 때"라는 문장을 보고 어떤 의미인지 모르고 지나갔는데, 찾아보니 최적을 전략을 선택해야하는 조건을 나타내는 말이었다.

그냥 단순히 홀짝 여부만 사용하면 쉽게 해결되는 문제이지만, DP를 사용하려면 이 조건이 필요했다.