from itertools import *
def find(seq):
start=end=0
for i in range(N+1):
if i!=seq[i]:
if not start:
start=i
end = i
return (start,end) if start else (1,1)
def Interval(seq,start,end):
interval = []; s = start
while s<=end:
interval.append(s)
e = s
while e<end:
if abs(seq[e+1]-seq[e])==1:
e += 1
else:
break
interval.append(e)
s = e+1
return interval
def reverse(seq,start,end):
return seq[:start]+[*reversed(seq[start:end+1])]+seq[end+1:]
N = int(input())
seq = [0]+[*map(int,input().split())]
start,end = find(seq)
seq0 = [i for i in range(N+1)]
for s,e in combinations(Interval(seq,start,end),2):
s1,e1 = min(s,e),max(s,e)
seq1 = reverse(seq,s1,e1)
start,end = find(seq1)
for s,e in combinations(Interval(seq1,start,end),2):
s2,e2 = min(s,e),max(s,e)
seq2 = reverse(seq1,s2,e2)
s3,e3 = find(seq2)
if reverse(seq2,s3,e3)==seq0:
result = [(s1,e1),(s2,e2),(s3,e3)]
for s,e in result:
print(s,e)
= 두 번 뒤집기 [백준 2505번] 두 번 뒤집기 (Python3) (tistory.com)
횟수만 다르고 똑같은 방식으로 풀었다.
두 번 뒤집기 문제를 브루트 포스로 풀어서 아쉬움이 약간 있었는데, 이 문제도 똑같이 풀리는걸 보니까 "뭐지? 내 풀이가 사실은 훌륭한 풀이였던건가?" 하는 생각이 들었다. 오히려 브루트 포스로 풀어서 모든 경우의 수를 커버할 수 있으니 횟수를 늘려도 범용성있게 활용할 수 있는 것 같다.
내가 처음이자 마지막으로 풀었던 다이아 문제가 라면사기[백준 18185번] 라면 사기 (Small) (tistory.com) 였는데, 그 문제는 결정적인 반례를 통한 힌트로 해결했었다. 하지만 이 문제는 처음으로 아무런 도움 없이 순수 자력으로 해결한 다이아 문제이기 때문에 뿌듯한 마음이 든다.
오늘의 교훈) 때로는 논리적인 풀이보다 브루트 포스가 낫다.