[백준 2561번] 세 번 뒤집기 (Python3)

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) 였는데, 그 문제는 결정적인 반례를 통한 힌트로 해결했었다. 하지만 이 문제는 처음으로 아무런 도움 없이 순수 자력으로 해결한 다이아 문제이기 때문에 뿌듯한 마음이 든다.

 

 

오늘의 교훈) 때로는 논리적인 풀이보다 브루트 포스가 낫다.