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

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

9658번: 돌 게임 4

 

---

• 문제

 

---

• 문제 풀이

백준 9658번 돌 게임 4는 이전에 풀었던 돌 게임 문제들과 상당히 유사하다. 백준 9658번 돌 게임 4를 풀기 전에 백준 9655, 9656, 9657번인 다른 돌 게임들을 먼저 풀기를 추천드린다.

 

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

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

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

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

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

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

 

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

 

다른 돌 게임 문제들과 비슷하게 이 문제에서도 가정이 하나 붙는다. 바로 상근이와 창영이가 이 돌 게임을 '완벽하게' 한다는 것이다. 이 말인즉슨 먼저 게임을 시작하는 상근이가 이기는 쪽으로 게임을 한다는 것이다.

 

예시를 한번 보겠다.

n = 1 : 상근이가 먼저 돌을 가져가므로 창영이가 이긴다.

n = 2 : 상근이가 돌을 1개 가져가고 남은 돌을 창영이가 가져가므로 상근이가 이긴다.

n = 3 : 상근이가 돌을 1개를 가져가거나 3개를 가져가도 마지막 돌은 상근이가 가져가므로 창영이가 이긴다.

n = 4 : 상근이가 돌을 3개 가져가면 남은 돌을 창영이가 가져가므로 상근이가 이긴다.

n = 5 : 상근이가 돌을 4개 가져가면 남은 돌을 창영이가 가져가므로 상근이가 이긴다.

n = 6 : 상근이가 돌을 3개 가져가면 마지막 돌을 창영이가 가져가게 되므로 상근이가 이긴다.

 

코드를 짤 때 다음과 같이 하면 된다.

 

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

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

 

상근이가 이기는 게 우선이므로 다음과 같이 코드를 짜면 된다.

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

 

---

• 코드

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

 

---

• 후기

이전에 풀었던 돌 게임 문제들과 상당히 유사해서 수월하게 풀 수 있는 문제였던 거 같다.