N,K = map(int,input().split())
last = 0
for n in range(1,N+1):
last = (K+last)%n
print(last+1)다이나믹 프로그래밍으로 해결하였다.
메모리 제한이 매우 작은것이 오히려 힌트가 되는 문제였다. 메모리 제한이 넉넉했다면 오히려 아이디어를 떠올리기 힘들었을 수도 있다. 하지만 메모리 제한은 매우 작은데 N의 범위는 500만이나 되다 보니, 크기 N의 배열을 이용하는 풀이나 세그먼트 트리나 팬윅트리같은 풀이를 애초에 배제할 수 있었고, 아이디어를 쉽게 떠올릴 수 있었다.
아이디어는 이러하다.
크기 n의 요세푸스 마지막 숫자가 x라고 가정하자.
n+1명의 사람들이 있을 때, 가장 먼저 제거되는 사람은 K번째 사람이다. 그럼 남은 사람들의 숫자는 n명이 된다. 그럼 나머지 n명에서 마지막 숫자는 아까 x라는 것을 구했다. 이때, K번째 사람을 제거했기 때문에, 시작숫자는 1부터가 아니라 K+1부터가 될 것이다.
즉, 크기 n의 요세푸스 마지막 숫자가 x라면, 크기 n+1의 요세푸스 마지막 숫자는 (x+K)%(n+1)이 되는 것이다.
점화식만 구하면 구현은 코드를 보면 알 수 있듯이 매우매우 간단하다.
오늘의 교훈) 때로는 문제의 제한사항이 힌트가 된다.