[백준] 9655번 : 돌 게임 - Java

문제

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

 

두 명의 플레이어가 번갈아 가며 돌을 가져가는 게임입니다. 각 플레이어는 한 번에 1개 또는 3개의 돌을 가져갈 수 있습니다. 마지막 돌을 가져가는 사람이 승리하게 됩니다. 게임은 항상 상근이가 먼저 시작합니다. 주어진 돌의 개수 N이 입력으로 주어질 때, 상근이가 이기는지 창영이가 이기는지 출력하는 문제

접근 방법

• DP 배열을 사용하여 각 돌의 개수에서 이길 수 있는지 여부를 저장합니다.
• 상근이가 돌을 1개 또는 3개 가져갈 수 있기 때문에, 돌의 개수가 N-1 또는 N-3일 때 상대방이 지는 경우, 현재 돌의 개수 N에서는 상근이가 이기게 됩니다.
• 돌의 개수가 1개 또는 3개일 때, 상근이가 이길 수 있습니다. (첫 번째로 가져가기 때문)
• 돌의 개수가 2개일 때는, 상근이가 1개를 가져가면 창영이가 1개를 가져가 승리하게 됩니다. 따라서 상근이는 질 수밖에 없습니다.

구현

DP 동적 계획법

• 돌이 1개일 때는 첫 번째 플레이어가 이기므로 dp[1] = true.
• 돌이 2개일 때는 첫 번째 플레이어가 1개를 가져가면 두 번째 플레이어가 1개를 가져가 이기게 되므로 dp[2] = false.
• 돌이 3개일 때는 첫 번째 플레이어가 3개를 모두 가져가 이기므로 dp[3] = true.
• 점화식 dp[i] = !dp[i-1] || !dp[i-3] 도출

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static boolean[] dp = new boolean[1001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        if (dp(N)) System.out.println("SK");
        else System.out.println("CY");
    }

    public static boolean dp(int n) {
        dp[1] = true;
        dp[2] = false;
        dp[3] = true;

        for ( int i = 4; i <= n; i++) {
            dp[i] = !dp[i - 1] || !dp[i - 3];
        }

        return dp[n];
    }
}

 

메모리:14336kb 시간:108ms