📜 문제
- 돌 N개를 차례로 가져갈 때, 마지막 돌을 가져가서 이기는 사람 구하기
- 완벽하게 게임을 하므로 필승법을 따를 것
- 한 번에 1개, 3개, 또는 4개를 가져갈 수 있음
우선, 돌 개수가 1,2,3,4 일 때 승자를 구하면 아래와 같이 나온다.
| 돌 개수 | 이기는 방법 | 승자 |
|---|---|---|
| 1 | 1 | 상근 |
| 2 | 1 / 1 | 창영 |
| 3 | 3 | 상근 |
| 4 | 4 | 상근 |
7까지 규칙을 나타내어 보면
| 돌 개수 | 이기는 방법 | 승자 |
|---|---|---|
| 5 | 3 / 1 / 1 | 상근 |
| 6 | 4 / 1 / 1 | 상근 |
| 7 | 1 / 4 / 1 / 1 | 창영 |
돌 개수가 5개인 경우, 3,1,1 의 경우로 상근이가 이긴다.
6개인 경우, 4,1,1의 경우로 상근이가 이긴다.
7개인 경우, 1,4,1,1의 경우로 창영이가 이긴다.
승자를 담은 배열 (이하 dp[n], n=돌 개수 )을 선언하고 4까지 초기화 해보자.
-
dp[5]의 경우, 상근이가 돌을 가져가는 개수에 따라 남은 돌이 4개, 2개 또는 1개가 남는다.
dp[4]와 dp[1]의 경우 상근이가 이기고, dp[2]의 경우는 창영이가 이긴다.반대로 말하면 상근이가 돌을 가져간 후 dp[4], dp[1]의 경우가 나오면 처음으로 두는 창영이가 이기고, dp[2]의 경우는 두 번째로 두게 되는 상근이가 이기므로 결과적으로는 상근이가 승자가 된다.
-
dp[7]의 경우, dp[6], dp[4], dp[3]의 경우가 나올 수 있다.
허나 위 3개의 경우는 모두 상근이가 이기는 경우이다.
따라서 상근이는 돌을 몇 개를 가져가도 질 수밖에 없다.창영이가 상근이가 돌을 가져간 후 남은
dp[6], dp[4], dp[3]의 경우에서 상근이가 이긴 방법대로 돌을 가져갈 것이기 때문이다.
위를 토대로 규칙을 도출하면, dp[i-1], dp[i-3], dp[i-4]가 모두 같은 값이면 dp[i]는 반대의 값 이 되고, 하나라도 다르다면 처음으로 두는 상근이가 승자가 된다.
✍ 부분 코드 설명
점화식을 통해 승자 구하기
boolean [] dp = new boolean [n+1];
dp[1] = true; // true: 상근 win, false: 창영이 win
for(int i=2;i<=n;i++){
if(i==2) dp[i]=false;
else if(i==3) dp[i]=true;
else if(i==4) dp[i]=true;
// 5부터 시작
else{
if(dp[i-1]==dp[i-3]==dp[i-4])
dp[i]=!dp[i-1];
else{
dp[i]=true;
}
}
}
dp 배열은 돌 개수 인덱스에 따른 승자를 담은 배열이다. (true:상근, false: 창영)
dp[i-1], dp[i-3], dp[i-4]가 모두 같은 경우 dp[i]에 반대 값을 넣는다.
하나라도 다른 경우, 우선으로 돌을 가져가는 상근이가 승자가 된다.
🍳 전체 소스 코드
package Algorithm.DP;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
돌 게임 3
기존 돌게임에서 돌을 1개, 3개 또는 4개를 가져갈 수 있음
*/
public class N_9657 {
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 [n+1];
dp[1] = true;
// true: 상근 win, false: 창영이 win
for(int i=2;i<=n;i++){
if(i==2) dp[i]=false;
else if(i==3) dp[i]=true;
else if(i==4) dp[i]=true;
// 5부터 시작
else{
if(dp[i-1]==dp[i-3]==dp[i-4])
dp[i]=!dp[i-1];
else{
dp[i]=true;
}
}
}
String winner = dp[n]?"SK":"CY";
System.out.println(winner);
}
}
✨ 결과
처음엔 N을 4로 나눈 나머지 값에 따라 승자가 결정되는가 싶었지만 10인 경우에 다른 값이 나와서 우회했다.
DP 문제집에서 찾은 문제를 푸니, 겁 먹지 않고 풀 수 있었다.
내 힘으로 문제를 풀어서 뿌듯하지만, 다음엔 풀이 시간을 더 줄이도록 해야겠다.
