BOJ 10923 - 정렬하기

BOJ 10923 - 정렬하기

어케 푸는지 모르겠는데 그냥 맞아버렸다.

일단 마지막에 어떻게 되는지를 직접 해본다.

그런다음 $d(i)$ 를 $i$가 마지막에 어느 위치에 가있는지에 대한 값으로 초기화하자.

$N$ 개의 수들이 계속 위치가 변하는 과정을 생각해보면 $N$ 개의 선이 계속해서 겹칠때 없이 움직이는 모양으로 생각할 수 있다.

$0$ 번째 수를 고려한다.

$0$ 번째 수가 현재 위치가 $x$ 이면 $d(0)$ 이랑 이걸 swap한다.

이제 $1$ 번째 수도 계속 $N$ 번을 진행하며 직접 구해준다.

이 방법이 유효한 이유는 $N$ 개의 선이 겹치지 않고, $0$ 번 째 수는 이미 $0$ 번째로 가는 라인으로 태워줬기 때문에 그 이후 과정에서 이 라인을 건드릴 일이 없기 때문이다.

나머지 $M-N$ 개는 $(0, 0)$ 으로 적당히 채워주도록 하자.