[백준 20004 파이썬] 베스킨라빈스 31 (실버4)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : △

https://www.acmicpc.net/problem/20004

소스 코드(파이썬)

import sys
input = sys.stdin.readline

A = int(input())

for i in range(1, A+1):
    gap = i+1
    
    if 30 % gap == 0:
        print(i)

풀이 요약

1. 베스킨라빈스 31의 오리지널 필승법을 알아보자.

   내가 30을 말하면 상대가 반드시 31을 말하게 된다. 즉, 상대가 30을 말하지 못하게 하면 된다.

   이 것은 내가 26을 말하면, 상대가 1에서 3까지 올릴 수 있는데, 1을 말해도 27이니까 내가 다음에 3번 올리면 30이고, 3을 말해도 29니까 내가 다음에 1번 올리면 30을 말할 수 있다.

   그리고 26을 말하는건 곧 상대가 26을 말하지 못하게 한다는 것과 같다. 위와 같은 원리로 22, 18, 14, 10, 6, 2를 상대가 말 못하게 하면 된다. 즉, 처음에 내가 2를 반드시 먼저 말해야 필승할 수 있다.

   꼭 3개의 수가 아니라 1~31의 모든 경우에 대해 이 원리는 성립한다. 규칙을 발견할 수 있는데, 상대가 말하지 못하게 할 수는 30으로부터 말할 수 있는 개수 n에 대해 n+1씩 줄어서, 0 이하가 되기 직전까지만 줄여주었을 때, 그 수를 선공이 먼저 말할 수 있으면 선공이 필승, 못 말하면 후공이 필승하게 된다.

   이 문제는 후공의 필승 경우를 찾는 문제이므로, 선공이 그 수를 못 말하는 경우, 즉 최대한 줄인 0 이상의 어떤 수가, 말할 수 있는 개수 n보다 크면 후공이 필승한다.

2. 구현은 간단하다.

   위 원리에 의해, 말할 수 있는 최대 개수 i에 대해,
   1) 30을 i+1로 나눈 나머지가 0일 때는 30부터 i+1씩 줄여서 0 이하가 되기 직전까지 줄인 어떤 수가 i+1이란 뜻이다. 즉, 선공은 최대 i까지만 말할 수 있으므로, 후공이 다음 턴에 i+1를 찍고갈 수 있으므로 후공이 필승할 수 있다.
   2) 나머지가 0이 아닐 때는, 최대한 줄인 어떤 수가 i+1보다 작다는 것을 의미한다. 즉 선공이 i까지 말할 수 있으니 그 수를 찍고갈 수 있고, 그래서 선공이 필승하게 된다.

   우리는 1)의 경우에만 i를 출력해주면 된다.

배운 점, 어려웠던 점

• 베스킨라빈스31의 필승법을 알면 쉽게 풀 수 있는 문제였다.