[Java] Baekjoon Online Judge 9655: 돌 게임

9655번: 돌 게임

💡문제

---

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

✏️입력

---

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

 

📑출력

---

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

예제입력 1

5

 

예제출력 1

SK

 

🔎알고리즘 분류

---

• 수학
• 다이나믹 프로그래밍
• 게임 이론

 

📌풀이

---

코드 1

package S5_9655_돌게임;

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 - 1], dp[i - 3]) + 1;
        }

        // 돌의 개수가 홀수이면 상근이(SK), 짝수이면 창영이(CY)가 승리
        if (dp[n] % 2 == 0) {
            System.out.print("CY");
        } else {
            System.out.print("SK");
        }
    }
}

이 문제는 주어진 돌의 개수에 따라 어떤 플레이어가 이길지 판단하는 문제이다.

 

돌 게임 규칙

플레이어는 1개 또는 3개의 돌을 가져갈 수 있다.
플레이어가 마지막 돌을 가져가면 이긴다.

 

동적 계획법 배열 dp를 이용하여 특정 돌의 개수에 대해 어떤 플레이어가 이길지 저장한다.
4개부터 주어진 돌의 개수까지의 결과를 계산하고, 돌의 개수가 홀수이면 상근이(SK), 짝수이면 창영이(CY)가 승리한다.

 

✔️동적 계획법 (Dynamic Programming)

---

동적 계획법은 최적화 이론의 한 기술로, 주어진 문제를 더 작은 부분 문제로 나누어 효율적으로 값을 구하는 알고리즘 설계 기법이다.

특히 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems)를 가지는 문제들에 적용된다.

 

핵심 아이디어

최적 부분 구조 (Optimal Substructure)

큰 문제의 최적해가 작은 부분 문제의 최적해를 이용해 구할 수 있어야 한다.

 

중복 부분 문제 (Overlapping Subproblems)

작은 부분 문제들을 해결하는 과정에서 동일한 부분 문제가 여러 번 발생하는 경우이다.

 

구현 방식

Top-Down (Memoization)

memo = {}

def dp_top_down(n):
    if n in memo:
        return memo[n]
    
    # Base case
    if n == 0 or n == 1:
        return n

    # Recursive cases
    result = dp_top_down(n - 1) + dp_top_down(n - 2)
    memo[n] = result  # Memoization
    return result

큰 문제를 해결하기 위해 작은 부분 문제를 호출하며, 중복되는 계산을 피하기 위해 이전에 계산한 결과를 저장한다.

 

Bottom-Up (Tabulation)

def dp_bottom_up(n):
    # Initialize table to store results
    table = [0] * (n + 1)
    table[0], table[1] = 0, 1  # Base cases

    # Fill the table
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]

    return table[n]

작은 부분 문제부터 시작하여 필요한 모든 결과를 테이블에 저장하며 큰 문제를 해결한다.

 

피보나치 수열에 적용

피보나치 수열은 동적 계획법의 대표적인 예시 중 하나로, 이전 두 항의 합이 다음 항을 이루는 수열이다.

 

Top-Down (Memoization) 방식

memo = {}

def fibonacci_top_down(n):
    if n in memo:
        return memo[n]

    # Base cases
    if n == 0 or n == 1:
        return n

    # Recursive cases
    result = fibonacci_top_down(n - 1) + fibonacci_top_down(n - 2)
    memo[n] = result  # Memoization
    return result

# Example usage
result = fibonacci_top_down(5)
print(result)  # Output: 5

이 코드에서 memo 딕셔너리는 이미 계산한 결과를 저장하기 위해 사용된다.

함수가 호출될 때마다 해당 값이 memo에 있는지 확인하고, 이미 계산된 값이 있다면 바로 반환한다.

 

Bottom-Up (Tabulation) 방식

def fibonacci_bottom_up(n):
    # Initialize table to store results
    table = [0] * (n + 1)
    table[0], table[1] = 0, 1  # Base cases

    # Fill the table
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]

    return table[n]

# Example usage
result = fibonacci_bottom_up(5)
print(result)  # Output: 5

이 코드에서는 반복문을 사용하여 작은 부분 문제부터 시작하여 큰 문제를 해결한다.

table 리스트에 중간 결과를 저장하면서 최종적으로 table[n]에 피보나치 수열의 값이 계산된다.