BOJ 1505 두 번 뒤집기

처음에는 오름차순 구간, 내림차순 구간을 구해서 각 구간을 구성하는 요소들의 모든 조합으로 다 해보고 일치하는지 찾아보려고 했는데... 많은 경우에 맞지만, 안 되는 경우도 있다는 것을 예제들을 만들어보면서 알게 되었다.

일단 2504문제에서 시간도 많이 뺐겼고, 공부할 것과 날 기다리고 있는 문제들이 매우 많기 때문에 이 문제의 해법을 검색해봤다.

해법은 다음과 같다.

  1, ..., n까지의 수열이 있다면 맨 앞의 수(1) 혹은 맨 뒤의 수(n)를 기준으로 차례대로 원래 위치와 비교해가면서 찾는 방식인데, 이게 어떻게 성립이 되느냐 곰곰히 생각해보니 두 번 다 뒤집어서 숫자들의 위치가 변했을 때, 맨 앞의 수(1)과 맨 뒤의 수(n) 둘 중 하나는 한 번 뒤집힐 수 밖에 없다. 반드시 둘 중 하나는 원래 위치에서 한 번 뒤집혀 바뀐 위치에 위치하므로 맨 앞 수나 맨 뒤의 수를 기준으로 뒤집은 구간을 찾아나가면 되는 것이다.

또한 맨 앞의 수나 맨 뒤의 수가 한 번 뒤집혀서 위치가 바뀌었을 경우, 그 뒤집은 구간의 경우의 수는 하나 밖에 존재하지 않는다.

그리고 맨 앞의 수나 맨 뒤의 수를 기준으로 해서 뒤집은 구간을 구한 후에는, 바로 그 다음 수로 하나씩 늘려나가면서(줄여나가면서) 확인해봐야 하는데, 이것 역시 이렇게 해야 경우의 수가 하나 밖에 존재하지 않기 때문인 것 같다.

일단 코드 짜봐야겠다.

열심히 하자!
복습하자!
준비된 자에게 기회가 온다.