백준 2661번 좋은수열

정보

문제 바로가기 [클릭]

난이도: Gold4

관련 개념: #백트래킹

---

조건

시간 제한	메모리 제한
1 초	128 MB

---

문제

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

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

• 33
• 32121323
• 123123213

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

• 2
• 32
• 32123
• 1232123

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

7

출력

1213121

---

코드(파이썬)

def check(num):
    tmp = stack + [num]
    len_tmp = len(tmp)-1
    for i in range(len_tmp//2+1):
        if tmp[len_tmp-1-2*i:len_tmp-i] == tmp[len_tmp-i:]:
            return False
    return True

def back_track(num):
    global still_find
    
    if len(stack) == n:
        print("".join(map(str, stack)))
        still_find = False
        return
    
    for i in nums[num]:
        if still_find and check(i):
            stack.append(i)
            back_track(i)
            stack.pop()

            
n = int(input())
nums = [[0, 0], [2, 3], [1, 3], [1, 2]]
still_find = True
stack = [1]
back_track(1)

---

특이사항

• 해결방법
  • 백트래킹으로 경우의 수 탐색
  • check 함수에서 현재 숫자를 추가했을 때 인접한 2개의 부분수열이 있는지 확인
  • 길이가 n인 수열을 찾았다면 still_find를 False로 변경해 백트래킹 종료

---

참고문헌

-