[Python 3] BOJ - 2478 "자물쇠"

 # 문제 링크

https://www.acmicpc.net/problem/2478

2478번: 자물쇠

 

 # 풀이

 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다.

 위의 그림 1은 n이 4일때 가능한 구간 뒤집기의 결과 중 일부이다. 문제에서 제시한 순서에 따라 자물쇠를 만들어야 하므로 한 번 왼쪽밀기를 했을 때, 인접한 두 수의 차이는 1 혹은 n - 1이 됨을 알 수 있다. 따라서, 위와 같이 연속하거나, 차이가 n - 1이 되는 수열만이 가능하다는 것은 자명하다. 

 그런데 이 때 size가 3일 때 2번째 예시와 size가 2일 때 3번째 예시처럼 크기가 작은 어떤 수열이 크기가 큰 다른 수열의 부분수열인 경우, 크기가 큰 수열은 크기가 작은 수열의 결과를 포함한다. 따라서, 굳이 모든 size에서 생성되는 수열을 일일이 매칭하지 않아도 된다. 즉, 가능한 수열 중 가장 큰 크기의 수열이 뒤집은 수열이 된다. 또한, 가능한 수열 중 가장 큰 크기의 수열이 아닌 더 작은 크기의 수열을 뒤집게 되면 절대로 입력을 만들 수 없다.

 그런데 뒤집은 수열을 다시 뒤집기 위해서는 두번째 왼쪽밀기를 이전 상태로 돌려야 한다. 따라서, 가능한 모든 왼쪽밀기에서 뒤집을 수 있는 수열을 찾았을 때, 그 때의 최대값이 실제로 뒤집은 수열이 된다. 이 때 뒤집을 수 있는 수열을 판별하는 방법은, 두번째 왼쪽밀기를 하기 전으로 되돌렸을 때의 상태에서 인접한 두 숫자의 차이가 1 혹은 n - 1인 연속된 수열을 찾으면 알 수 있다

 

 # 코드

import sys

# 입력부
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

# res : (뒤집는 시작점, 뒤집는 끝점, 두번째 왼쪽밀기의 정도)를 저장하는 리스트
res = []
for i in range(n - 1, 0, -1):
    # temp : 두번째 왼쪽밀기를 원래대로 되돌린 수열
    temp = arr[i : n] + arr[ : i]
    # cnt : 뒤집기가 가능한 수열의 크기
    cnt = 0
    # start : 뒤집기가 가능한 수열의 시작점
    start = -1
    for j in range(n - 1):
        # 현재 수가 1이 아니라면 1, 현재 수가 1이라면 n - 1의 차이가 나는 경우만 가능
        if (temp[j] - 1 > 0 and temp[j + 1] == temp[j] - 1) or (temp[j] - 1 == 0 and temp[j + 1] == n):
            cnt += 1
            # 시작점 갱신
            if start == -1:
                start = j
    # 뒤집기가 가능하면 저장
    if cnt > 0:
        res.append((start, cnt, i))
        
# 크기 순 정렬
res.sort(key=lambda x : (-(x[1] - x[0])))
# 두번째 왼쪽 밀기 이전으로 되돌림
arr = arr[res[0][2] : n] + arr[ : res[0][2]]
# 뒤집기 이전으로 되돌림
arr = arr[:res[0][0]] + arr[res[0][0] : res[0][1] + 1][::-1] + arr[res[0][1] + 1 : n]
# idx : 처음 왼쪽 밀기를 한 후 1의 인덱스
idx = arr.index(1)

# 정답출력
print(n - idx)
print(res[0][0] + 1, res[0][1] + 1)
print(n - res[0][2])