[JAVA]백준 22846번: 인증된 쉬운 게임

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

22846번: 인증된 쉬운 게임

 

1. 문제 설명

 

모니터에 1이 쓰여있고, 칼리와 링고가 번갈아가면서 모니터에 쓰여있는 수의 약수를 하나 선택해 모니터에 있는 값에 더한다.

이때 제한 K를 초과한 사람이 패배하게 된다.

 

각자 최선의 전략으로 플레이를 한다고 가정하자.

 

K가 주어졌을 때 이기는 사람은?

 

2. 풀이

 

DP로 풀 수 있는 문제이다.

 

모니터의 값이 x일 때부터 시작할 때 Kail가 이기면 True를 저장하는 dp배열을 선언해서 게임을 제한 값 K부터 시작한다.

 

제한 값 K부터 시작하는 이유는 K 초과하는 범위는 탐색할 필요가 없기 때문이다. (Kali의 차례에 K를 초과하면 지기 때문에 굳이 확인해보지 않아도 됨)

 

현재 모니터의 값이 x라면, Kail는 x의 약수를 모니터에 더할 수 있기에 x의 약수를 구해줘야 한다.

 

약수를 구하는 방법에는 여러 가지가 있는데, 아래 코드에서는 시간을 단축하기 위해서 제곱해서 x와 같거나 작은 수의 범위만 약수를 탐색했다.

 

만약 y가 x의 약수라면 Kail는 현재 값 x에 y를 더해 x+y 값을 만들 수 있다.

 

Kali가 모니터의 값이 x일 때 y를 더해서 이기기 위해서는 2가지 경우를 확인해야 한다.

 

먼저, x+y가 K 이하인지이다.

 

x+y가 K를 초과하게 된다면 Kail가 지는 것이므로 Kail가 이기기 위해서는 x+y가 K 이하여야 한다.

 

두 번째는, dp [x+y] 값이 false인지이다.

 

이것을 이해하기 위해서는 Kali가 이기는 최선의 전략에 대해서 생각해봐야 한다.

 

Kali가 이기는 최선의 전략이란 무엇일까?

 

바로 Ringo가 지는 것이다.

 

따라서 Kali가 모니터 값 x에 y를 더하면 Ringo는 모니터 값 x+y에서부터 게임을 시작하는 것과 같고 Ringo가 

모니터 x+y 값에서부터 게임을 시작해서 진다면?(dp [x+y]==false)

 

그것이 바로 Kail가 이기는 것이다.

 

따라서 이 두 가지 경우를 체크하여 두 조건이 모두 참이라면 dp [x]를 true로 변경한다.

 

K부터 1까지 반복문을 진행한 후 dp [1]의 True/False 값으로 Kail가 이겼는지 Ringo가 이겼는지 판단한다.

 

이 문제가 어려웠다면, 비슷한 알고리즘의 다른 문제들을 풀어보는 것을 추천한다..!

 

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

11062번: 카드 게임

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

10714번: 케이크 자르기 2

3. 코드

// JAVA 11, 시간 200ms, 메모리 29428KB
// DP로 문제 해결

import java.io.*;


public class Main {

    // 자연수 K
    public static int K;
    // dp 배열
    // 모니터의 값이 x일때부터 게임을 시작할때 Kali가 이기면 True, 지면 False
    public static boolean [] dp;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        K = Integer.parseInt(br.readLine());

        dp = new boolean[K+1];

        for (int x = K; x >= 1; x--) {
            // 시간 절약을 위해 y*y<=x 인 범위만큼만 약수 확인
            for (int y = 1; y * y <= x; y++) {

                if (x % y == 0) {
                    // x에 y를 더했을 때 범위를 벗어나지 않고 x에 y를 더한 값이 false 일 때 true
                    // 범위를 벗어날 경우 자동적으로 지는 것이기 때문에 범위 벗어나면 안됨

                    // Kali의 다음 차례는 Ringo
                    // Kali가 이기는 최선의 전략은 Ringo가 지는 경우
                    // 따라서 x에 y를 더해 Ringo의 차례를 갔을 때 dp의 값이 False라면 dp[x]=true
                    if (x + y <= K && !dp[x + y]) {
                        dp[x]=true;
                        break;
                    }
                    // y*y<=x인 경우만큼만 구했기에 x/y도 추가적으로 구해줘야 함.
                    if (x + x / y <= K && !dp[x + x / y]) {
                        dp[x]=true;
                        break;
                    }
                }

            }
        }


        // 초기 모니터의 숫자가 1이기 때문에 dp[1]의 값을 비교
        // Kali가 1부터 시작해서 이긴다면 (dp[1]=True)라면 Kali 출력
        if (dp[1]) {
            bw.write("Kali");
        } else {
            bw.write("Ringo");
        }




        bw.flush();

    }

}