[백준] 9657번 : 돌 게임 3

문제

 

 

접근 방식

DP로 풀 필요도 없이 규칙만 찾으면 연산 한 줄로도 풀 수 있는 문제지만 그냥 DP로 풀어봤다.

 

우선 DP 테이블은 불리언 타입의 1차원 배열로 생성한 후에

상근이가 이기는 경우를 true, 창영이가 이기는 경우를 false로 채워주면 된다.

 

자기 순서에 1, 3, 4개 중 한 번씩 가져갈 수 있으니 이 경우에 상근이는 무조건 이길 수 있고

1, 3, 4번의 초기값은 true로 설정해준다.

 

9까지 직접 계산해 가며 표를 만들어보면 알 수 있는데

n번째 수를 가져가는 경우 중 상근이가 한 번이라도 가져가는 경우가 있다면

무조건 상근이가 이기는 경우이기 때문에

상근이가 처음에 1개를 가져가거나 3개를 가져가거나 4개를 가져간 후에

창근이가 지는 경우가 한 번이라도 있다면 상근이가 이기는 것이 된다.

dp[i] = (!dp[i - 1 || !dp[i - 3] || !dp[i - 4])

 

즉, 위와 같은 풀이가 나오게 된다.

 

이 문제는 n의 범위가 1,000 이하이기 때문에 dp 테이블이 설정이 가능하지만

같은 문제에 n의 범위만 int 형을 벗어난 돌 게임 6 문제 같은 경우에는

배열을 선언할 수 없기 때문에 다른 방법으로 풀어야 한다.

 

처음에 언급했던 것처럼 이 문제는 더 간단하게 풀 수 있는데

n을 7로 나눈 나머지가 0이거나 2인 경우에만 상근이가 지기 때문에

한 줄 만으로도 풀 수 있는 문제다.

 

풀이

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        boolean[] dp = new boolean[1001];
        
        dp[1] = dp[3] = dp[4] = true;
        
        for (int i = 5; i <= n; i++) {
            dp[i] = (!dp[i - 1] || !dp[i - 3] || !dp[i - 4]);
        }
        
        System.out.println(dp[n] ? "SK" : "CY");
    }
}