턴을 번갈아가며 돌을 1개 또는 3개 가져가는 게임에서의 승자를 구하는 문제
처음에는 DP라 생각했는데, 몇 번 손으로 해보니 DP보다도 더 간단하게 풀 수 있는 방법을 알아냈다.
5 = 3x1 + 1x2 = 1x5 –> 총 홀수번 시행 후 게임 종료
10 = 3x3 + 1x1 = 3x2 + 1x4 = 3x1 + 1x7 = 1x10 –> 총 짝수번 시행 후 게임 종료
즉, 돌을 세 개씩 가져가든 하나씩 가져가든 누구의 턴에서 게임이 종료되는지에는 영향을 미치지 않는다는 것이다. 따라서 돌을 세 개 가져간 횟수와 하나 가져간 횟수를 더해 그 수의 짝/홀 여부만 판별하면 된다!
나는 게임을 가장 빨리 끝내는 경우(3개 이상의 돌이 있으면 무조건 3개를 가져가는 방식)으로 체크했는데, 지금 생각해보니 그냥 N이 짝수인지 홀수인지만 확인하면 된다..
간단한 풀이
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
int ones = N % 3; // 돌을 한 개씩 가져간 횟수
int threes = N / 3; // 돌을 세 개씩 가져간 횟수
if ((ones + threes) % 2 == 0) cout << "CY" << endl;
else cout << "SK" << endl;
system("pause");
return 0;
}
갑자기 생각난 더 간단한 풀이
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
if (N % 2 == 0) cout << "CY" << endl;
else cout << "SK" << endl;
system("pause");
return 0;
}
DP로도 풀어보았다.
상근이를 기준으로 dp[i]는 N=i일 때 상근이가 이기는지 여부(1: 이김, 0: 짐)를 의미한다.
둘이서 하니까 전에 1이었으면 0으로, 0이었으면 1으로 바꿔주기만 하면 된다.
오랜만에 algorithm 헤더 include에서 내장 min 쓰는 대신 매크로를 써봤다 ㅎㅎ
#include <iostream>
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
using namespace std;
int main() {
int N, i;
cin >> N;
int dp[1001] = { 0, }; // dp[i]: N=i일 때 상근이가 이기는지 여부(1: 이김, 0: 짐)
dp[1] = 1;
dp[2] = 0;
dp[3] = 1;
for (i = 4; i <= N; i++) {
if (MIN(dp[i - 1], dp[i - 3]) == 0) dp[i] = 1;
else dp[i] = 0;
}
if (dp[N]) cout << "SK" << endl;
else cout << "CY" << endl;
return 0;
}