Platinum 1
문제 분석
N개가 남아있을 떄 최소 몇개를 가져가면 무조건 게임을 승리할 수 있는지 하나씩 세보자.
일단 k개를 선택했다고 하면, 만약 상대가 (N−k)개에서 (1∼2k)만큼 뺐을 때, 무조건 승리할 수 있으면 된다.
즉, 우선 N−3k>0을 만족하고,
dp[N−k−1]≦2, dp[N−k−2]≦4 ⋯ dp[N−3k]≦4k
를 모두 만족하는 k를 구할 수 있다.
이 사실을 통해 초반 수열을 구해보자.
규칙 찾기
나온 수열은 다음과 같다.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
---|
1 | 2 | 3 | 1 | 5 | 1 | 2 | 8 | 1 | 2 | 3 | 1 | 13 | 1 | 2 | 3 | 1 | 5 | 1 | 2 | 21 | 1 | 2 |
여기서 일단 dp[i] = i 인 것의 수열을 보면 1,2,3,5,8,13,21.. 이고 피보나치 수열이다.
아닌 경우에는 마지막으로 피보나치 수였던 곳 부터 다음 피보나치 수까지 dp[1~]이 반복된다.
풀이
N이 피보나치 수임을 판별하자.
피보나치 수는 굉장히 빠른 속도로 증가하기 때문에 N이하의 모든 피보나치수를 짧은 시간 안에 찾을 수 있다.
만약 N이 피보나치 수라면 N을 출력한다.
아니라면 N보다 작은 최대의 피보나치수를 N에서 뺀다.
위 과정을 반복한다.
고찰
왜 되는지 잘 모르겠다. 증명을 찾아보려고 했으나 실패했다.. 피보나치수와 왜 연관이 있는걸까.
Platinum 2
문제 분석
누가 봐도 그런디 문제임을 알 수 있다.
하지만 N,M의 제한이 굉장히 크므로 또 규칙을 찾아야만 할 것 같다.
일단 N,M이 20이하일 때에 대해서 그런디 수를 찾아보자.
규칙 찾기
001120311033224052001120311033224052111111111111111111111111111111111111221112111211111211001120311033224052331113111311111311111111111111111111111111111111111111001120311033224052331113111311111311331113111311111311221112111211111211221112111211111211441114111411111411001120311033224052551115111511111511221112111211111211
하.. 잘 모르겠다. 하지만 여기서 알 수 있는 사실은 만약 dp[1][k]가 0인 k의 집합을 S라고 할 때,
S의 임의의 두 원소(중복 가능)를 뽑아 좌표를 구하면 그 곳의 그런디 수는 0임을 알 수 있다.
그리고 한 행에 대해서 좀 더 많이 수를 뽑아 봤다. 그랬더니 놀랍게도.. 첫 두 행을 제외하고 34를 주기로 같은 그런디 수가 나타는 것을 볼 수 있었다..!
풀이
다음과 같이 답을 낼 수 있다.
{1,2,6,10,16,22,26,30,36,40,44,56,60,646,10,22,26,30+34nif≦68else
고찰
34라는 기괴한 숫자를 마주한게 이번이 처음이 아니다.숫자 카드 제거 게임 여기에서도 만났었는데 이해할 수가 없다. 그냥 34라는 주기를 기억하고 경험치로 먹어놔야 겠다. 찾은 숫자를 그대로 박는데 16을 빠뜨려서 두번 틀렸다. 좀 빡친다.
풀고 있는 알고리즘 리스트(Platinum V 이상)