[백준/Python] 2661번 - 좋은 수열

문제

백준 2661번 - 좋은 수열

해결 과정

• 백트래킹으로 풀기

• 나쁜 수열이라면 -1 반환하면서 빠져나오기

  • 현재 확인중인 입력값의 절반만 반복하면 전체 수열 확인 가능

  • ex) 12131213

  • range = 1,2,3,4

    i	$s[- i :]$	$s[-2 * i:-i]$
    1	[3]	[1]
    2	[1,3]	[1,2]
    3	[2,1,3]	[1,3,1]
    4	[1,2,1,3]	[1,2,1,3]

  for i in range(1,(depth//2)+1):
    if s[-i:] == s[-2*i:-i]:
      return -1

• depth가 n자리 수 라면 출력
  • 작은 수부터 확인하기 때문에 작은 값인지 비교없이 바로 출력
  • 0을 반환하면 함수 종료
• depth가 n자리 수가 아니라면 배열에 계속 넣어서 확인하기

풀이

import sys

n = int(sys.stdin.readline())
s = []

def back(depth):
  # 나쁜 수열이라면 -1 반환하면서 빠져나오기
  for i in range(1,(depth//2)+1):
    if s[-i:] == s[-2*i:-i]:
      return -1
      
  # n자리 수
  if depth == n:
    for i in range(n):
      print(s[i],end = '')
    return 0
      
  for i in range(1,4):
    s.append(i)
    if back(depth+1) == 0:
      return 0
    s.pop()

back(0)

https://sungmin-joo.tistory.com/66