백준 2605 두번 뒤집기

문제의 핵심은 두 번 뒤집는다는 것이다.

문제가 너무 어려웠다. 초등학생은 대단하구나.

참고한 코드

위 링크를 봐서 해결방법을 봤는데 정말 좋았다. 핵심은 다음과 같다.

1. ==1 혹은 n 의 위치는 정해져있다.== 맨 앞이나 맨 뒤다.

   : 1과 n이 둘 다 동시에 두 번 뒤집히는 경우는 없다. (그런 경우라면 그냥 원래 수열이 나올 뿐이다.)

2. 처음에는 1을 먼저 앞으로 빼본다. 그리고 변경된 수들에서 다음 수인 2를 찾는다.
3. 2가 원래 위치와 맞는 숫자라면 다음 수인 3을 찾고, 틀리다면 2를 찾아서 다시 뒤집어 본다.
4. 두 번 뒤집어도 값이 나오지 않으면 이번에는 맨 처음 수들에서 n값으로 찾아본다.
5. 위 과정을 다시 반복하다보면 둘 중 하나에서는 반드시 정답이 나온다.

그리고 이 방법에서 생각해야 했던 핵심은 한 번 뒤집었을 때 자기자리로 돌아오려면 indexof(a[i])와 i를 뒤집어야 한다는 것.