[백준/Python] 2561 세 번 뒤집기

문제 링크

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

문제 난이도

다이아몬드 5

문제 설명

주어진 순열을 정렬된 상태로 만들기 위해서 3번 이하의 교환으로 가능한지를 판별하는 문제입니다. 교환은 연속된 수열을 뒤집는 방식으로 이루어집니다. 주어진 순열을 가능한 한 적은 횟수로 정렬된 상태로 만들어야 합니다.

문제 풀이

아이디어

이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

1. 비정상 구간 확인: 순열에서 연속된 숫자 간의 차이가 1보다 큰 부분과 단조증가 또는 단조감소가 아닌 부분을 확인합니다.
2. 비정상 구간 뒤집기: 비정상 구간을 뒤집어서 순열을 정렬된 상태로 만드는 방법을 찾습니다.
3. 백트래킹: 백트래킹을 이용해 최대 3번의 교환으로 문제를 해결합니다

해당 풀이가 가능한 이유는 실제로 비정상 구간의 개수가 그리 많지 않다는 것입니다.

상세 구현

1. 입력과 초기화:
   • 입력을 받아서 순열을 배열에 저장하고, ans 리스트를 초기화합니다.
2. 비정상 구간 확인 함수 (check):
   • 순열에서 비정상 구간을 찾아서 반환합니다. 비정상 구간은 숫자 차이가 1보다 큰 부분과 단조증가 또는 단조감소가 아닌 부분입니다.
3. 백트래킹 함수 (bt):
   • 현재 상태에서 비정상 구간을 확인하고, 비정상 구간이 없으면 답을 출력합니다.
   • 비정상 구간이 있으면 최대 3번의 교환으로 문제를 해결하려고 시도합니다. 교환 후 다시 백트래킹을 진행합니다.

코드

from sys import stdin
input=stdin.readline

def check():
    points=[]
    for i in range(1,n+2):
        if abs(arr[i]-arr[i-1])>1:
            points.append((i-1,i))
    for i in range(1,n+1):
        if not (arr[i-1]<arr[i]<arr[i+1] or arr[i-1]>arr[i]>arr[i+1]):
            points.append((i,i))
    return points

def bt(dep):
    case=check()
    if not case:
        for i in ans:
            print(*i)
        for i in range(3-len(ans)):
            print(1,1)
        exit()
    if dep==3:
        return
    for ii in range(len(case)):
        for jj in range(ii+1,len(case)):
            i=case[ii][1]
            j=case[jj][0]
            for k in range((j-i)//2+1):
                arr[i+k],arr[j-k]=arr[j-k],arr[i+k]
            ans.append((i,j))
            bt(dep+1)
            for k in range((j-i)//2+1):
                arr[i+k],arr[j-k]=arr[j-k],arr[i+k]
            ans.pop()

n=int(input())
arr=[0]+list(map(int,input().split()))+[n+1]
ans=[]

bt(0)

풀이 설명

1. 입력 처리:
   • 첫 줄에 숫자의 개수 n을 입력받고, 두 번째 줄에 n개의 숫자를 리스트로 입력받습니다.
   • 입력받은 순열 앞뒤에 0과 n+1을 추가하여 배열을 초기화합니다. 처음과 끝이 뒤집힌 경우를 해당 구현을 통해 해결할 수 있습니다.
2. 비정상 구간 확인:
   • check 함수는 두 가지 조건을 기반으로 비정상 구간을 찾습니다:
     1. 두 숫자의 차이가 1보다 큰 경우.
     2. 단조증가 또는 단조감소가 아닌 경우.
3. 백트래킹:
   • 비정상 구간이 없으면 현재까지의 교환 과정을 출력하고 종료합니다.
   • 비정상 구간이 있으면 최대 3번의 교환을 시도하여 정렬된 상태를 만들 수 있는지 확인합니다.
   • 교환 후 상태를 되돌리는 과정도 포함하여 백트래킹을 수행합니다.

이와 같은 과정을 통해 주어진 순열을 3번 이하의 교환으로 정렬된 상태로 만들 수 있는지 판단하고, 백트래킹을 통해 얻은 바꾸는 구간을 출력하면 됩니다. 만약 3번보다 적은 횟수로 바꿀 수 있다면, 남은 횟수만큼 1 1과 같이 아무렇게 자기 자신을 뒤집어주면 해결 할 수 있습니다.