백준 2661번 파이썬 | 좋은 수열 (BackTracking)

문제

숫자 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들 사이에는 빈칸을 두지 않는다.

 

---

풀이

이 문제는 백트랙킹으로 풀었다.

완전탐색? DFS? 와 비슷하게 가면서 중간에 확인할 가치가 없는 값이면 그 즉시 중단하고 다음것을 찾는다.

이 문제의 핵심은 1,2,3 순으로 검사하는 것이라고 생각한다.

결국에는 최소값을 찾아야 하는데 좋은 수열이면서 최소값인 것을 1,2,3순으로 찾으면 결국 제일 먼저 발견하는 값이 최소값이 되니까 그 즉시 return 0을 해버린다.

check 함수에서는 이게 좋은 수열인지 나쁜수열인지 파악해 주는 함수고 backTracking에서는 이것을 처음에 체크하면서 반복된다. 나쁜 순열이면 그 즉시 종료.

# 2661 좋은 수열

import sys
input = sys.stdin.readline


def check(result, count):
    for k in range(count):
        sliceTemp = result[k:]
        for i in range(1, len(sliceTemp) // 2 + 1):
            checkV = sliceTemp[:i]
            if checkV == sliceTemp[i:i + i]:
                return False
    return True


def backTracking(count):
	
    # 나쁜 순열이면 그즉시 종료
    if not check(result, count):
        return -1
    if count == N:
        print(*result, sep="")
        return 0
    # 핵심. (1,2,3 순으로 진행하기에 결국엔 먼저 되는값이 최소값)
    for i in range(1, 4):
        result.append(i)
        if backTracking(count + 1) == 0:
            return 0
        result.pop()


N = int(input())
result = []
backTracking(0)