[자바]백준 9656번 돌 게임2 [다이나믹프로그래밍][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

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

9656번: 돌 게임 2

문제 설명

이 문제는 배스킨라빈31과 비슷한 문제 같다 ㅎㅎㅎ

배스킨라빈31은 마지막 숫자인 31을 부르면 지는 게임인데, 이건 마지막 돌을 가져가면 지는 것이다.

단, 가져가는 사람은 1개 혹은 3개만 가져갈 수 있다.

해설

해당 문제는 정말 정말 정말 쉽게 풀 수 있다.

잘 보면 1과 3만 가져갈 수 있으면 이기는 방법은 내 순서에 2 or 4가 오면 된다.

그럼 나한테 2나 4가 오려면 그전에는 6이나 8이 오면 되고.. 뭐 이런 식으로 가다 보면 결국 짝수가 나오면 첫 번째 순서가 이기고 홀수가 나오면 두 번째 순서가 이긴다.

 

근데 짝수, 홀수로 문제를 풀면 도움 될게 없으니 위의 방법을 dp(다이내믹 프로그래밍)로 풀어보겠다.

상근이를 기준으로 문제를 풀겠다.

 

• 상근이 순서에 0이 오면 이긴다.
• 상근이 순서에 1이 오면 진다.
• 상근이 순서에 2가 오면 이긴다.
• 상근이 순서에 3이 오면 2를 만들거나 진다. 2를 만들면 창영이가 1을 만들어서 진다.
• 상근이 순서에 4가 오면 이긴다.
• 상근이 순서에 5가 오면 2나 4를 만들게 되고 창영이가 1개나 3개를 선택해서 지게 된다.
• 상근이 순서에 6이 오면 창영이에게 5개나 3개를 넘길 수 있고 창영이가 1개나 3개를 선택하면 2개나 4개가 오게 되어 이긴다.

정리

상근이 입장에서는 상근이 자신에게 0개 혹은 창영이에게 1개를 넘겨야 이긴다.

돌게임, 베스킨 라빈스31 게임 이런 게임들은 결국 N개에서 N - 1개 혹은 N - 3개 를 넘기고 또 여기서 -1개 혹은 -3개를 넘겨서 결국에 하나하나 거쳐오면서 마지막에 0개인지 1개인지 알고나서 승부가 나는 것이다.

그렇다면 이걸 반대로 생각하면 N개수가 마지막에 나에게 0이 오는지 1이 오는지 알면 된다. 

0이 오는지 1이 오는지는 어떻게 아는 것일까?

바로 N - 1개 혹은 N - 3개가 0인지 1인지 알면 된다.

결국 그럼 dp를 활용해 0부터 N까지 순차적으로 올라가면서 0인지 1인지 기록해 주면 된다.

 

나머지는 코드를 보고 설명하겠다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1 + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 0;
        
        for (int i = 3; i <= n; i++) {
            int cy = i - 1;
            dp[i] = dp[cy - 1];
        }
        
        System.out.println(dp[n] == 0 ? "SK" : "CY");
        br.close();
    }
}

배열 길이를 n + 1 + 1을 해준 이유

위에서 코드를 보면 +1을 해준 이유는 0,1,2를 직접 데이터를 넣어줄 것인데, n이 1이라면 에러가 발생하기 때문에 n이 1이 나오더라도 에러가 발생하지 않게 +1을 해주는 것이다.

dp[i - 1]만 해주고 dp[i - 3]을 안 해준 이유

돌을 3개를 가져가지 않고 1개만 가져가도 결과는 똑같기 때문이다.

만약 -1도 해줘야 하고 -3도 계산해줘야 한다면 -1과 -3 중에 하나라도 0 이 있으면 이기는 걸로 쳐주면 된다.

근데 -1과 -3 중에 0이 있는지 계산을 해보면서 발견한 건데 -1이나 -3이나 결과가 똑같다는 것이다.

cy와 cy - 1은 무엇인가?

cy는 창영이가 갖게 될 돌의 개수이고

cy - 1을 해줘서 다시 상근이에게 넘기는 것이다.

그러고 cy - 1이 이길 수 있는 돌의 개수인지 dp[i] 에 넣어준 것이다.

 

상근 1번 -> 창영 2번 -> 상근 3번...

이런 식으로 게임이 진행되는데 dp 배열에는 1번에는 기록이 되어 있지 않고 3번에 기록되어 있기 때문에 창영이에게 한번 건네주고 창영이가 준 돌의 개수의 dp를 가져와서 dp[i]에 넣어준 것이다.

 

물론 창영이 순서인 2번에도 기록은 되어있지만 2번으로 dp[i]에 넣어주려면 + 1해 주고 %2를 해주는 계산식이 더 들어가서 3번으로 계산해 주는 게 좋다.

 

으아... dp문제는 설명하기 너무 어렵다... 잘 설명한 걸까..  허허