[백준] 2661 - 좋은수열 / Python / 골드 4

🚩문제 주소

📄풀이

재귀

나쁜 수열이 있는지 확인하는 check함수, check함수를 활용해 조건에 맞춰 수를 늘려가는 재귀 함수로 나눕니다.


check함수

• [1,2,3,1,2,3]인 예시가 있다면 3-2 -> 3,1-2,3 -> 1,2,3-1,2,3 순으로 확인합니다. 1,2,3-1,2,3이 존재하여 나쁜 수열이므로 이 수열은 정답이 되지 않습니다.
• False가 반환되지 않으면 좋은 수열이므로 True를 반환합니다.

requr함수

• 1,2,3을 수열에 각각 추가해보고 check함수를 통과한다면 수열에 숫자를 넣고 재귀합니다.
• 수열의 길이가 주어진 N과 같다면 수열을 출력하고 종료합니다.

👨‍💻코드

def check(nums):
  for i in range(1, len(nums)+1):
    if nums[-(i*2):-i] == nums[-i:]:
      return False
  return True

def requr(idx, nums):
  if idx == N:
    print(nums)
    exit()
  
  for i in '123':
    if check(nums+i):
      requr(idx+1, nums+i)

N = int(input())
requr(1, '1')