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

 

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

9656번: 돌 게임 2

 

---

 

• 문제

 

---

• 문제 풀이

백준 9656번 돌 게임 2는 DP (다이나믹 프로그래밍)를 이용해서 푸는 문제이다. DP에 대해서 조금 더 알고 싶으면 밑에 있는 링크를 참고해 주면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

이 문제에서는 상근이와 창영이가 턴을 번갈아가면서 돌을 가져가며, 돌은 1개나 3개를 가져갈 수 있다. 그리고 마지막 돌을 가져가는 사람이 게임을 지게 되고 돌 n개가 있을 때 누가 지는 지를 구하면 되는 실버 4 난이도의 DP 문제이다.

 

예를 한번 보겠다.

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

n = 2 : 처음에 상근이가 1개를 가져가고 창영이가 남은 1개를 가져가면 되므로 상근이가 이긴다.

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

n = 4 : 상근이가 돌 1개를 가져가든, 3개를 가져가든 돌이 1개나 3개가 남으므로 상근이가 이긴다.

• ㅋ

→ 1개를 가져갔을 경우 : 4개가 남고 창영이가 1개를 가져가든 3개를 가져가든 1개나 3개가 남으므로 창영이가 이긴다. 

→ 3개를 가져갔을 경우 : 2개가 남고 창영이가 1개만 가져갈 수 있으므로 창영이가 이긴다.

 

이 문제는 1차원 int형 배열로 풀 수 있다. 이 예시들로 본 것처럼 돌을 1개를 가져가는 경우, 그리고 3개를 가져가는 경우 둘 다 고려해야 한다. 

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

 

Math.min 함수를 사용한 이유는 문제에 나온 것처럼 상근이와 창영이가 게임을 완벽하게 하기 때문에 최솟값을 구해야 한다. 그리고 dp [n]이 홀수면 창영이가 이기는 게임이고 dp [n]이 짝수면 상근이가 이긴다.

 

---

• 코드

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

 

---

• 후기

백준 9655번 돌 게임과 거의 똑같은 문제였다. 만약에 백준 9655번도 참고하고 싶으면 밑에 링크를 참고하면 되겠다.

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

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