BOJ_9656 : 돌 게임 2

👉 문제링크

9656번: 돌 게임 2

---

---

🔸 문제 분석 🔸

• n개의 돌이 있을때, ab 두 사람이 턴마다 1개 혹은 3개를 가져갈 수 있고 마지막 돌을 가져가면 패배한다.
  • 두 사람이 완벽하게 게임을 한다고 했을때 상황을 그려보면 다음과 같다. 
    • n=1 : a >> b승리
    • n=2 : a b >> a승리
    • n=3 : a b a >> b승리
    • n=4 : a a a b >> a승리
  • 홀수는 b승리, 짝수는 a의 승리라는 것을 알 수 있다.
• n이 최대 1000이고 시간 복잡도는 O(n)이므로, 제한시간 1초는 널널하다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        if (n % 2 != 0)
            System.out.println("CY");
        else
            System.out.println("SK");
    }
}

🔸 코드 해석 🔸

• n이 홀수면 "CY", 짝수면 "SK"를 출력한다.

---

🔸 end 🔸

• 간단한 문제였지만, 문제를 잘못 이해하고 베스킨라빈스31 게임규칙으로 적용해서 헤맸던 문제이다.
  • 풀고보니 너무 쉬운데 너무어렵게 접근했었다...
• 다 풀고보니 태그에 DP가 있는걸 알았다. (풀이 포스팅 을 참고했다)
  • DP로 어떻게 풀 수 있을까 생각해보면 다음과 같은 점화식을 구할 수 있다.
    • dp[n] = Math.min(dp[n-1], dp[n-3]) + 1;
  • 완벽한 게임을 한다고 했으므로, 뽑는 횟수를 최소로 만드는 경우를 찾으면 된다.
  • 뽑는 횟수가 홀수는 a승, 짝수면 b의 승리이다.