[AC] 2505-두번 뒤집기

출처 : https://www.acmicpc.net/problem/2505 (정확히는 정보올림피아드 문제이다.)

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2505.cpp

이 문제의 경우 정말 어렵지 않다. 다만 처음에 이렇게 생각하기가 참 힘들다. 이래서 알고리즘을 공부하나보다. 정말 역발상으로 하면 풀리는 문제였다.

우선 이 문제에 먼저 집중해야할 부분은 스페셜 저지라는 점이다. 답은 여러개라는 말이다. 

문제를 보면 입력이 주어지는데 이 입력된 수들은 2번 뒤집혔다는 말이다. 문제가 이해가 되지 않는다면 다시 읽어보면 된다.
알고리즘 공부를 한다면 문제 이해는 기본중의 기본이다. 문제가 정말 잘못되어 이해하지 못한경우라면 정답자도 없을 것이다.

암튼 나의 알고리즘은 이렇다.

1. 1 혹은 n값의 위치는 정해져있다. 즉 맨앞이거나 맨 뒤이다. 우선 여기에 초점을 맞춘다.

2. 처음엔 1을 먼저 앞으로 빼본다. 그리고 변경된 수들에서 다음 수인 2를 찾는다.

3. 2가 원래 위치와 맞는 숫자라면 다시 다음수인 3을 찾고, 틀리다면 2를 찾아서 다시 뒤집어 본다.

4. 두번 뒤집어도 값이 나오지 않으면 이번엔 맨 처음 수들에서 n값으로 찾아본다.

5. 위 과정을 다시 반복하다보면 둘중 하나에서는 반드시 정답이 나온다.

고등학생문제보니 3번 뒤집기가 있다. 이건 다르게 생각해봐야할 것 같다. 아직 풀지는 않았지만, 이 문제와는 아주 다른 해결책이 있을것이다.

정보올림피아드는 이런 방법을 허용하지 않고, 보통 비슷한 문제를 전혀다른 해결책으로 풀게 한다. 하지만 1과 n값의 위치가 포인트일것이다. 

굳이 이 수들이 앞에 있는데 뒤로 보냈다가 다시 앞으로 보내는 번거로움은 하지 않을것 같다.