7570 줄 세우기

1~N번의 사람이 아무 순서로 놓아져 있다. 이 때 각 번호의 사람을 맨 앞, 맨 뒤로 보내는 방법으로 오름차순 정렬하려 할 때, 최소 몇번 보내야 하는가를 알아내는 문제이다.

이전에 풀었던 줄 세우기 문제와 비슷한데, 다른점은 이전것은 어디로 보내도 괜찮았지만, 이번 문제는 맨 앞이나 맨 뒤로만 보내야 한다는 점이다.

이 문제를 풀기위해선 먼저 어떤것을 밝혀내야 최소를 구할 수 있는가를 알아내야 한다. 많은 고민을 통해 알아낸것은 다음가 같다.

카운트를 0으로 초기화 하고, 자기 바로 다음 번호가 자신의 뒤에 위치해있다면 카운트를 1 증가시키고 그 다음 숫자에 대해 똑같이 반복해준다.

이 때 카운트가 최대인 경우를 구해서 N - 최대를 해주면 답이 나온다.

이유는 예를통해 설명해보자.

5 2 4 1 3 이라는 숫자가 있다면, 위 방법을 통해 찾아보면

2 3 이 연속되므로 최대치는 2이고 답은 5 - 2 = 3이다.
2와 3을 고정 시키고 2 와 3 사이에 있는 4 , 1 과 나머지를 앞이나 뒤로 빼버리면 되기 때문이다.

2 4를 고정시키면 3을 2와 4 사이에 넣어야 하므로 4를 움직여야만 한다. 따라서 고정이 불가능하다.

따라서 연속된 숫자만이 사이에 넣을 필요가 없으므로 고정이 가능하다.

줄 세우기 문제는 어떤 숫자를 고정시킬지가 중요한것 같다.

소스