https://www.acmicpc.net/problem/20004
시간 1초, 메모리 512MB
input :
- A이 주어진다. (1 ≤ A ≤ 31)
output :
- 시온이가 게임을 이길 수 있는 n을 한 줄에 하나씩 오름차순으로 출력
조건 :
- 시온이가 게임을 이길 수 있는 모든 n(1 ≤ n ≤ A)을 출력
접근을 생각하지 못했다...
그냥 재귀로 풀어야 하나 싶었다...
그러나, DP 처럼 생각을 했어야 했다.
만약 현재 n = 3 일때. 선공의 기준에서.
남은 수가.
1개 => 패배
2, 3, 4 => 승리
5개 => 패배
6, 7, 8 => 승리
9 => 패배.
이와 같이 (31 % n + 1) == 1 일 때 선공이 패배를 한다.
그리하여 위의 식을 성립하는 n들을 찾아서 출력해주자.
import sys
a = int(sys.stdin.readline())
ans = []
for i in range(1, a + 1):
if 31 % (i + 1) == 1:
ans.append(i)
for item in ans:
print(item)
