태현이는 "나누고 밀기"라는 게임을 하는 중이다. 게임은 1번부터 N번까지 순서대로 번호가 붙은 N개의 슬롯을 사용한다. 기본적으로 M번 슬롯에 사탕이 있는데, 사탕을 다음의 "나누기" 명령과 "밀기" 명령을 이용해 최소 명령 횟수로 1번 슬롯으로 옮기는 것이다.

"나누기"명령은 N을 나누는 임의의 소수 p를 골라서 슬롯들을 번호 순서대로 p개의 연속된 구간으로 나눈다. 따라서 처음 구간은 1 번 부터 N/p 번 슬롯이 포함된 구간이고, 그 다음은 N/p+1 번 부터 2N/p 번 슬롯이 포함된 구간이 두번째 구간이된다. 나뉜 구간 중에서 옮기려고 하는 사탕이 있는 구간만을 남기고 나머지 구간에 존재하는 슬롯을 버린다. 남은 슬롯의 수가 새로이 N으로 바뀌고, 슬롯의 번호가 작은 순서대로 1, 2, ..., N번 번호가 붙게된다.

두번째 명령은 "밀기" 명령인데 i번 슬롯에 사탕이 있을 경우 이를 i-1번이나 i+1번으로 옮기는 연산이다. i-1번으로 옮기는 연산을 왼쪽으로 밀기라고 하고, i+1번으로 옮기는 연산을 오른쪽으로 밀기라고 한다. 만약 1번 슬롯에 사탕이 있을 경우 왼쪽으로 밀기를 할 경우에는 N번으로 옮겨지고, N번에서 오른쪽으로 밀기를 할 경우에는 1번으로 옮겨진다.

두개의 명령을 잘 조합하여, 명령을 수행하는 횟수를 최소화 하여 1번 슬롯으로 사탕을 옮기는 프로그램을 작성하라.

#2480 upload 6 done 4 how_to_reg 4

나누고 밀기 timer 1s memory - MB

#2480

나누고 밀기 1s - MB