[백준-자바] N_9657 돌 게임 3

0woy·2024년 1월 17일
0

코딩테스트

목록 보기
7/40

📜 문제

  • 돌 N개를 차례로 가져갈 때, 마지막 돌을 가져가서 이기는 사람 구하기
  • 완벽하게 게임을 하므로 필승법을 따를 것
  • 한 번에 1개, 3개, 또는 4개를 가져갈 수 있음

우선, 돌 개수가 1,2,3,4 일 때 승자를 구하면 아래와 같이 나온다.

돌 개수이기는 방법승자
11상근
21 / 1창영
33상근
44상근

7까지 규칙을 나타내어 보면

돌 개수이기는 방법승자
53 / 1 / 1상근
64 / 1 / 1상근
71 / 4 / 1 / 1창영

돌 개수가 5개인 경우, 3,1,1 의 경우로 상근이가 이긴다.
6개인 경우, 4,1,1의 경우로 상근이가 이긴다.
7개인 경우, 1,4,1,1의 경우로 창영이가 이긴다.

승자를 담은 배열 (이하 dp[n], n=돌 개수 )을 선언하고 4까지 초기화 해보자.

  • dp[5]의 경우, 상근이가 돌을 가져가는 개수에 따라 남은 돌이 4개, 2개 또는 1개가 남는다.
    dp[4]와 dp[1]의 경우 상근이가 이기고, dp[2]의 경우는 창영이가 이긴다.

    반대로 말하면 상근이가 돌을 가져간 후 dp[4], dp[1]의 경우가 나오면 처음으로 두는 창영이가 이기고, dp[2]의 경우는 두 번째로 두게 되는 상근이가 이기므로 결과적으로는 상근이가 승자가 된다.

  • dp[7]의 경우, dp[6], dp[4], dp[3]의 경우가 나올 수 있다.
    허나 위 3개의 경우는 모두 상근이가 이기는 경우이다.
    따라서 상근이는 돌을 몇 개를 가져가도 질 수밖에 없다.

    창영이가 상근이가 돌을 가져간 후 남은 dp[6], dp[4], dp[3]의 경우에서 상근이가 이긴 방법대로 돌을 가져갈 것이기 때문이다.

위를 토대로 규칙을 도출하면, dp[i-1], dp[i-3], dp[i-4]가 모두 같은 값이면 dp[i]는 반대의 값 이 되고, 하나라도 다르다면 처음으로 두는 상근이가 승자가 된다.


✍ 부분 코드 설명

점화식을 통해 승자 구하기

      boolean [] dp = new boolean [n+1];
        dp[1] = true; // true: 상근 win, false: 창영이 win
        
        for(int i=2;i<=n;i++){
            if(i==2) dp[i]=false;
            else if(i==3) dp[i]=true;
            else if(i==4) dp[i]=true;
            
            // 5부터 시작
            else{
                if(dp[i-1]==dp[i-3]==dp[i-4])
                    dp[i]=!dp[i-1];
                else{
                    dp[i]=true;
                }
            }
        }

dp 배열은 돌 개수 인덱스에 따른 승자를 담은 배열이다. (true:상근, false: 창영)

dp[i-1], dp[i-3], dp[i-4]가 모두 같은 경우 dp[i]에 반대 값을 넣는다.
하나라도 다른 경우, 우선으로 돌을 가져가는 상근이가 승자가 된다.


🍳 전체 소스 코드

package Algorithm.DP;

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

/*
돌 게임 3
기존 돌게임에서 돌을 1개, 3개 또는 4개를 가져갈 수 있음
 */
public class N_9657 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        boolean [] dp = new boolean [n+1];
        dp[1] = true;
        // true: 상근 win, false: 창영이 win
        for(int i=2;i<=n;i++){
            if(i==2) dp[i]=false;
            else if(i==3) dp[i]=true;
            else if(i==4) dp[i]=true;
            // 5부터 시작
            else{
                if(dp[i-1]==dp[i-3]==dp[i-4])
                    dp[i]=!dp[i-1];
                else{
                    dp[i]=true;
                }
            }
        }
       String winner =  dp[n]?"SK":"CY";
        System.out.println(winner);
    }
}

✨ 결과

처음엔 N을 4로 나눈 나머지 값에 따라 승자가 결정되는가 싶었지만 10인 경우에 다른 값이 나와서 우회했다.

DP 문제집에서 찾은 문제를 푸니, 겁 먹지 않고 풀 수 있었다.
내 힘으로 문제를 풀어서 뿌듯하지만, 다음엔 풀이 시간을 더 줄이도록 해야겠다.


0개의 댓글