백준 9655: 돌 게임 [실버 Ⅴ / Java]

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

9655번: 돌 게임

---

 

• 알고리즘 : 수학 or Dynamic Programming
• 풀이 날짜 : 과거, 2023.06.27. 리뷰

 

 

< 풀이 설명 >

 

출처 : 나무위키

 

"베스킨 라빈스 31" 게임같은 문제이다.

중학교 때 수학 학원 선생님이 해당 게임을 두 명이서 할 때 이기기 위해서는 26을 선점해야 한다고 말해주셨던 기억이 난다. 그럼 22를, 18, 14, 10, 6, 2 를 먼저 사수하면 유리하다.

 

 

 

각설하고, 이 문제는 위의 게임과 다르게 1개나 3개만 가져갈 수 있고, 마지막 돌을 가져가는 사람이 이긴다.

 

여기서 가져갈 수 있는 돌 개수가 홀수임을 알 수 있다.

그럼 먼저 시작하는 상근이는 무조건 1(▷2, 4), 3(▷4, 6), 5(▷6, 8), 7(▷8, 10), ... 로 홀수 번째 돌을,

창영이는 무조건 짝수 번째 돌을 가져가서 이긴다.  

그래서 두 줄로도 풀 수 있는 문제이다.

if (N % 2 == 1) System.out.println("SK");
else System.out.println("CY");

 

 

 

위 논리를 DP로도 표현해 보자.

 

배열 dp[ i ] 를 i 개의 돌이 있을 때 진행되는 turn 수 라고 정의 한다면,

dp[i - 3]이나 dp[i - 1] 중에서 선택해 주면 된다.

`완벽하게 게임을 했다` 라고 하므로 둘 중 최솟값을 골라주면 된다.

 

dp[1] = 1 (상근)

dp[2] = 2 (상근 ▷창영)

dp[3] = 1 (상근)

dp[4] = Math.min(dp[1], dp[3]) + 1 = 2 (상근 ▷창영)

dp[5] = Math.min(dp[2], dp[4]) + 1 = 3 (상근 ▷창영 ▷ 상근)

...

dp[i] = Math.min(dp[i - 3], dp[i - 1]) + 1

 

dp[i] 값이 홀수일 때는 상근, 짝수일 때는 창영이가 이긴다.

 

 

 

< 筆者의 辯 >

`완벽하게 게임을 한다`를 잘 이해해야 한다.

 

처음에 상근이와 창영이가 이기기 위해 최선의 수를 둔다고 생각했고

BR31 게임처럼 먼저 선점해야 하는 돌 번호를 구해야 하나 라고 생각했다.

 

하지만 단순히 예를 들어 3일 때를 생각해보자.

3개의 돌이 있을 때, 가능한 턴의 경우는

a. 상근(1) ▷ 창영(1) ▷ 상근(1)

b. 상근(3) 이다.

후자가 `완벽하게 게임`을 한다는 의미이다.

 

단순히 N이 정해지면 이기는 사람은 정해져 있고,

어차피 이길 거 상대방한테 희망고문 하지 않고 바로 게임을 끝내는 것이다.

 

따라서 이 문제는 그냥 N을 1과 3들의 최소한의 조합으로 표현하면 된다.

처음에 무조건 3개씩 가져가고, 3n + 1, 3n + 2개째 돌은 하나씩만 가져가면 된다.

다음 문제랑 원리가 비슷하다.

[백준/Greedy] - 백준 2839: 설탕 배달 [실버 Ⅳ / Java]

 

 

 

< 코드 >

1) DP

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());
        int[] dp = new int[1001];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 1;
        for (int i = 4; i <= N; i++) dp[i] = Math.min(dp[i - 3], dp[i - 1]) + 1;

        if (dp[N] % 2 == 1) System.out.println("SK");
        else System.out.println("CY");
    }

}

 

2) 수학

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 == 1) System.out.println("SK");
        else System.out.println("CY");
    }

}

 

 

< 결과 >

위에 부터  2) 번, 1) 번 코드