농부 창호에게는 N(3≤N≤50,000) 마리의 소가 있다. 소들한테는 전부 1번부터 N번까지 일련번호가 붙어 있다. 따라서 소들을 일렬로 서게 해서, 앞에 있는 소부터 번호를 취한 수열은 일종의 N자리의 N진수가 된다.

저녁시간이 되면 창호의 소들은 아무렇게나 늘어서서 밥 먹기를 기다린다. 하지만 창호는 그들이 아무렇게나 늘어서는 걸 싫어하기 때문에, 소들과 타협을 했다. 일단 그들이 아무렇게나 늘어선 다음에 창호가 원하는 대로 자리를 바꾸기로 하되, 제약을 두기로 한다.

창호는 왼쪽 자리부터 번호를 취한 수열을 N자리의 N진수로 볼 때, 이 수를 최소화할 수 있도록 소들이 줄서기를 원한다.

위에서 말한 제약이란, 소들끼리 위치가 바뀐다면 한 자리에 원래 있던 소의 일련번호와, 새로 그 자리에 들어온 소의 일련번호의 차이가 1이하로 차이가 나야 하는 것이다. 다시 일련번호가 3인소가 있던 자리에는 2번이나 3번, 4번소밖에 들어오지 못한다. (차이에서는 0의 차이도 허용이 된다.)

만약 8마리의 소가 “8 5 7 3 6 4 2 1”과 같은 순서대로 서 있다고 할 경우, 위의 제약 조건을 만족시키면서 수열을 통해 만들어지는 N자리의 N진수 중 최소가 되는 경우는 “7 4 8 2 6 3 1”로 배치하는 것이다.

원래 소들의 배치가 주어질 때, 이 제약을 지키면서 소들이 재배치될 수 있는 방법을 찾자.

#1480 upload 6 done 3 how_to_reg 3

저녁식사 timer 1s memory - MB

#1480

저녁식사 1s - MB