[백준] 2478 자물쇠 - 파이썬 (Python)

백준 2478 자물쇠 - 파이썬 (Python)

문제

링크

문제 링크: https://www.acmicpc.net/problem/2478

주의

1. 밀기 횟수는 1 <= k < N 입니다. 즉, 아예 밀지 않거나 N번 밀어서 밀기 전과 같게 할 수 없습니다.

2. 뒤집기 구간은 [p,q] 이고, p < q 입니다. 즉, 반드시 2개 이상의 원소를 뒤집어야 합니다.

발상

원래의 동작을 반대로 실행하여 원본 ( [1,2,3, ..., n] )이 나온다면 정답입니다.

우선 자물쇠를 문제의 그림처럼 일자 형태로 생각하지 않고, 양 끝이 붙어있는 원의 형태로 생각합니다.

1. 자물쇠는 맨 처음에 연속성을 가지고 있습니다. (인접한 두 원소 간의 차이 = 1 / 맨 앞과 맨 뒤의 경우만 예외)

2. 구간 뒤집기를 실행하면 대부분의 경우 연속성이 파괴됩니다. (파괴 되지 않는 경우가 존재하고 이는 이후에 예외로 다룹니다.)

3. 입력으로 주어진 자물쇠를 한 칸씩 오른쪽으로 밀어보며 연속성이 파괴된 구간을 모두 찾습니다. (인접한 원소끼리의 차이가 1이 아닌 경우, 양 끝 값은 예외)

4. 3번의 결과를 가지고 실제로 구간 뒤집기를 실행해 봅니다.

5. 4번의 결과로 연속성을 가지게 된 뒤집기 구간이 있다면, 이를 한 칸씩 오른쪽으로 밀어보며 원본 배열과 같아지는 지 확인하고 같다면 정답으로 출력합니다.

예외 사항

위의 발상은 연속성이 파괴된 구간을 찾아서 문제를 해결하는 방법입니다.

하지만 몇 가지 경우에는 구간 뒤집기를 실행하여도 연속성이 파괴되지 않습니다.

완전한 반대 방향이 되었을 뿐, 연속성은 사라지지 않았습니다.

위의 발상에서, 1과 8은 양 끝이기 때문에 연속 되는 것으로 간주하였습니다.

1~N 구간을 뒤집고 왼쪽으로 1번 민 결과와 같습니다.

마찬가지입니다.

1~N 구간을 뒤집고 왼쪽으로 N-1번 민 결과와 같습니다.

이 세가지 경우는 따로 처리를 해야합니다.

앞서 말씀드렸다시피, 세 가지 경우는 모두 방향이 반대일 뿐 연속성은 가지고 있습니다.

따라서, 이를 반대로 이용하여 위의 세가지 중 하나를 실행한다면 원래 방향의 연속된 자물쇠가 나오게 됩니다.

이후에는 처음에 미는 횟수와 마지막에 미는 횟수만 적절히 조절해주면 답이 될 수 있습니다.

코드