이번 문제는 백준의 실버 3 문제 돌 게임 3 문제이다.
문제가 생각보다 잘 풀리지 않아서 생각을 정리해보려 한다.
상근이가 항상 게임을 먼저 시작하고, 1 3 4개의 돌을 가져갈 수 있다.
이 때 게임을 반드시 번갈아 할 때 승자를 정해달라고 한다.
돌의 갯수에 따라 승자는 반드시 정해져있는 게임이다.
먼저, 이런 경우에는 갯수에 따른 승자를 다 적어보는게 맞다고 생각한다.
1개일 때 부터 차근차근 승자를 적어보자.
경우의 수
1개 SK
1개의 돌만 있을 때는 반드시 상근이가 이긴다.
2개 CY
2개의 돌이 있을 때는 반드시 창영이가 이긴다.
상근이가 1개 가져가고, 창영이가 1개 가져간다.
3개 SK
3개의 돌이 있을 때는 반드시 상근이가 이긴다.
4개 SK
4개의 돌이 있을 때는 반드시 상근이가 이긴다.
이제 관건은 5개부터 승자를 생각하는 것이다.
5개 SK
5개의 돌이 있을 때는 상근이가 이긴다.
3 1 1과 같이 가져가면, 상근이가 이기게 된다.
6개 SK
6개의 돌이 있을 때는 상근이가 이긴다.
4 1 1과 같이 가져가면, 상근이가 이기게 된다.
7개 CY
7개의 돌이 있을 때는 창영이가 이긴다.
상근이가 몇 개로 시작을 해도, 반드시 창영이가 이긴다.
8개 CY
8개의 돌이 있을 때는 상근이가 이긴다.
상근이가 몇 개로 시작을 해도, 반드시 창영이가 이긴다.
DP
위의 경우의 수들을 적으면서 곰곰히 생각해보았다.
N개의 돌로 게임을 한다면, 이전 단계를 이용할 수 있지 않을까?
만약 8개의 돌로 게임을 할 때, 상근이가 먼저 4개를 가져간다면?
그럼 이제 창영이가 먼저 돌을 가져가고 4개로 게임을 하는게 된다.
그 말인 즉슨, 4개로 하는 돌 게임의 결과를 반대로 하면 된다는 것이다.
4개로 하는 돌 게임은 상근이가 이기니 답은 CY이다.
그럼 상근이가 먼저 3개를 가져가면?
창영이가 먼저 돌을 가져가고 5개로 게임을 하는게 되니, CY이다.
1개를 먼저 가져가면?
창영이가 먼저 돌을 가져가고 7개로 게임을 하는 것이니, SK가 된다.
이 때, 답은 SK로 상근이가 이기는 것이다.
그 판단은, 하나의 경우라도 CY로 끝난 게임이 있는지로 판단한다.
왜냐하면 마지막에 창영이가 돌을 가져갔다면, 반드시 상근이가 이기기 때문이다.
즉, N-1 N-3 N-4번째 게임에 대해 돌을 마지막으로 가져간 사람에 따라
승패가 갈리며, 한 번이라도 창영이가 가져갔으면 상근이가 이긴다.
구현 코드는 아래와 같이 간단하다.
int main() {
cin >> num;
init_dp();
for (int i = 5; i <= num; i++) {
if (dp[i - 1] == true || dp[i - 3] == true || dp[i - 4] == true)
dp[i] = false;
else
dp[i] = true;
}
if (dp[num] == false)
cout << "SK";
else
cout << "CY";
return 0;
}