[백준] 9657번 : 돌 게임 3 – JAVA [자바]

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

9657번: 돌 게임 3

 

---

• 문제

 

---

• 문제 풀이

백준 9657번 돌 게임 3은 이전에 풀었던 백준 9655번 돌 게임, 백준 9656번 돌 게임 3의 연장된 문제이며 상당히 유사하다. 백준 9657번 돌 게임 3을 풀기 전에 백준 9655번과 백준 9656번을 먼저 푸는 것을 추천드린다.

 

https://propercoding.tistory.com/entry/백준-9655번-돌-게임-–-JAVA-자바

[백준] 9655번 : 돌 게임 – JAVA [자바]

https://propercoding.tistory.com/entry/백준-9656번-돌-게임-2-–-JAVA-자바

[백준] 9656번 : 돌 게임 2 – JAVA [자바]

 

이 문제에서는 돌 n개가 있고 마지막 돌을 가져가는 사람이 이기는 게임이 바로 돌 게임 3이다. 상근이가 먼저 게임을 시작하며 돌을 1개, 3개, 또는 4개를 가져갈 수 있다.

 

예시를 한번 보겠다.

 

n = 1 : 상근이가 돌 1개를 가져가면 끝나므로 상근이가 이긴다.

n = 2 : 상근이는 처음에 돌 1개만 가져갈 수 있고 나머지 1개를 창영이가 가져가므로 창영이가 이긴다.

n = 3 : 상근이가 돌 3개를 가져가면 끝나므로 상근이가 이긴다.

n = 4 : 상근이가 돌 4개를 가져가면 게임이 끝나므로 상근이가 이긴다.

n = 5 : 상근이가 처음에 3개를 가져가고, 창영이가 1개를 가져가면 마지막 돌을 상근이가 가져가므로 상근이가 이긴다.

n = 6 : 상근이가 4개를 가져가고, 창영이가 1개를 가져가면 마지막 돌을 상근이가 가져가므로 상근이가 이긴다.

 

이 문제에서는 가정이 하나 붙는다. 바로 두 사람이 '완벽하게' 게임을 한 다는 것이다. 이 문제에서 완벽하게라고 함은 바로 상근이가 이기는 쪽으로 게임을 한다는 것이다. 상근이가 먼저 게임을 시작하기 때문이다. 

 

즉 int형 배열 dp를 만들고 for-loop을 돌려 Bottom-up 형식으로 밑에서부터 배열을 채워 나가면 된다.

int[] dp = new int[1001];
for (int i = 5; i <= n; i++) {
    dp[i] = 2;
    if (dp[i-1] % 2 == 0 || dp[i-3] % 2 == 0 || dp[i-4] % 2 == 0) {
        dp[i] = 1;
    }
}

dp [n]이 1이면 상근이가 이기고 dp [n]이 2이면 창영이가 이긴다.

 

---

• 코드

 

import java.util.*;
import java.io.*;
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;
        dp[4] = 1;
        for (int i = 5; i <= n; i++) {
            dp[i] = 2;
            if (dp[i-1] % 2 == 0 || dp[i-3] % 2 == 0 || dp[i-4] % 2 == 0) {
                dp[i] = 1;
            }
        }
        if (dp[n] == 1) {
            System.out.print("SK");
        } else {
            System.out.print("CY");
        }
    }
}

 

---

• 후기

이전에 풀었던 백준 9655번과 백준 9656번이랑 유사한 문제여서 쉽게 풀 수 있는 문제였다.