[맛있는물회] [파이썬] <백준 알고리즘> 2661번 "좋은 수열"

문제 조건

---

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

 

Input

---

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

 

Output

---

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

생각한 아이디어

---

요즘 시험이다 뭐다 알고리즘 풀이를 꾸준히 안했더니 잘 안풀리는 것 같다.

자꾸 어려운 문제들을 건드려서 그런건지 감이 떨어진건지,,, 쉽지않다!

 

이번 문제도 정답률이 50프로인데 꽤 어려웠고, 시간이 많이 걸렸다 ㅜㅜ

 

 

메모에 적힌것 처럼 백트래킹을 하는 문제이다.

 

여기서 가장 중요한 부분은 정답이 나오면 재귀를 나갈 수 있냐 없냐에 달려있다.

이 문제에서 원하는 답은 가장 작은 수열이므로 1, 2, 3으로 진행한다면 가장 먼저 n길이만큼 나오는 값이 정답이다. 

하지만 깊이 우선 탐색인 DFS로 풀게되면 정답을 찾아도 다시 그전 값으로 돌아가 재귀를 진행하게 된다.

 

여기서 재귀를 빠져나오기 위해서 return을 0으로 두고 만약 return이 0이면 다시 return 0을 하게 하면서 재귀를 빠져나올 수 있다.

 

나쁜 수열의 판단은 브루트포스로 싹다 비교해 줘야한다.

 

소스코드

#2661 좋은수열

import sys
import re
input=sys.stdin.readline

ans=int('9'*81)
def dfs(val):
   global ans
   if len(val)==n:
      if ans>int(val):
         ans=int(val)
      return 0
   for i in range(1,4):
      tmp =val+str(i)
      flag=0
      for k in range(1,len(tmp)//2+1):
         if tmp[-k:]==tmp[-2*k:-k]:
            flag=1
            break
      if flag==1:
         continue
      else:
         if dfs(tmp)==0:return 0
n=int(input())
dfs('')
print(ans)

 

*파이썬 문법 정리