백준 22846 인증된 쉬운 게임 - C++
https://www.acmicpc.net/problem/22846
22846번: 인증된 쉬운 게임
게임 공장의 공장장인 stonejjun은 올해도 게임을 만들어내고 있다. 만들어진 게임은 검수를 거쳐 캐릭터 팀에서 만든 캐릭터들이 플레이를 하고, 이를 문제 팀에서 문제로 만들게 된다. 올해는 정
www.acmicpc.net
요새 뭔가 게임 문제들만 풀어서 작성하는거 같은데..
<문제>
게임 공장의 공장장인 stonejjun은 올해도 게임을 만들어내고 있다. 만들어진 게임은 검수를 거쳐 캐릭터 팀에서 만든 캐릭터들이 플레이를 하고, 이를 문제 팀에서 문제로 만들게 된다.
올해는 정말 쉬운 게임 문제를 하나 만들라는 여론이 많았기에, stonejjun은 하는 수 없이 자문위원들에게 인증을 받은 쉬운 게임을 만들게 되었다. 그렇게 세상에 탄생한 문제가 바로 이 문제이다.
칼리와 링고는 쉬운 게임을 한다. 모니터에는 1이 쓰여있고, 칼리부터 번갈아 가면서 게임을 진행한다. 둘은 자신의 차례에 모니터에 쓰여있는 수의 약수를 하나 선택해 모니터에 있는 값에 더한다. 이때 제한 K를 초과한 사람이 패배하게 된다.
캐릭터 팀에서 만들어진 캐릭터는 게임을 할 때 최선의 전략으로 플레이를 하게 된다. K가 주어졌을 때 누가 이기게 되는지 구해보자!
칼리가 이기게 된다면 Kali를 링고가 이기게 된다면 Ringo를 출력한다.
<제한 사항>
1초, 1024MB, 1<= K <= 10^5
<규칙>
초기 모니터에는 1이 쓰여있고,
각 플레이어는 약수를 모니터에 쓰여있는 수의 약수를 더 할수 있다.
입력된 K를 넘어가는 플레이어가 패배
<풀이>
사실 혼자 오랜 시간 고민했는데 결국 어떻게 풀지 생각이 나지 않아, Slack 그룹에서 다른 분의 설명을 듣고 풀고, 이렇게 기억에 남기기 위해서 블로그에 포스팅 하게 되었다.
처음 딱 보고 든 생각이 DP다. K의 값에 따라 값이 결정되고, 변하지 않을 것이다.
그리고, 꼭 최선의 수를 알아야 할 필요는 없을 것이다. 이정도는 까지는 금방 생각이 닿았는데,
문제는 이 이후에 규칙을 세우는 게 어려웠다. 나중에 더 검색해보니, n * sqrt(n)으로도 풀리긴 풀렸다는 것 같지만, 조금 더 명쾌한 풀이가 알고 싶었다.
K를 임의의 자연수라고 하면, K는 1부터 N까지 연속된 자연수들을 약수로 가지고, N+1은 약수로 가지지 않는 어떤 자연수 N이 항상 존재할 것이다. 그러면 K - (N+1)을 만약 상대 플레이어부터 넘겨 받는다면, 바로 K로 직행할 수 있을까?
N+1은 K의 약수가 아니고, 그에 따라 자연스럽게 K - (N+1)의 약수도 아닐 것이다.
그러면 K - (N+1)에서 만들 수 있는 수는 K - i로 i는 ( 1<= i <= N)이다. i는 이 범위에서 항상 K의 약수이기 때문에,
K- i 또한 i를 약수로 가진다.
그에 따라서, DP[K] = DP[K-(N+1)]로 수에 따른 승, 패를 정할 수 있다.
<후기>
요즘 백준 문제들을 오히려 기계적인 테크닉만 사용해서 풀어서 이런 생각을 못한 거 같다.
테크닉 적용이 힘들다면, 손으로 여러 경우를 해보거나, 수학적으로 접근해보자.
#include <iostream>
using namespace std;
using ll = long long;
bool dp[100100];
// 백준 22846 인증된 쉬운 게임
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// 초기 모니터에는 1이 쓰여있고,
// 각 플레이어는 약수를 모니터에 쓰여있는 수의 약수를 더 할수 있다.
// 입력된 K를 넘어가는 플레이어가 패배
int k;
cin >> k;
dp[1] = false; dp[2] = true;
dp[3] = false; dp[4] = false;
dp[5] = false; dp[6] = true;
dp[7] = false;
// K가 1 ~ N 까지 연속된 자연수를 모두 약수로 가지고, N+1은 약수가 아니라고 하면,
// K - (N+1)이 화면에 올라와 있으면? K로 바로 갈 수 없고, K - i (1<=i<=N) 로 오게 된다.
// i는 전제에 따라 항상 K - i의 약수이기 때문에, K - i에서 항상 K로 갈 수 있다.
// 즉, K - (N+1)을 받으면 받은 사람의 패배이다.
// 7의 경우, N = 1 => 5를 받으면 받으면 패배
// 8의 경우, N = 3 => 5를 받으면 패배
int i, j;
for (i = 8; i <= k; i++) {
for (j = 2;; j++) {
if ((i % j)) break;
}
dp[i] = dp[i - j];
}
if (dp[k])
cout << "Kali";
else
cout << "Ringo";
return 0;
}