[Python / BOJ 2661] 좋은 수열

 

https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

 

 

0. 문제

1, 2, 3으로만 이루어진 수열이 있다. 길이 N(1이상 80이하)인 좋은 수열 중 가장 작은 수열을 찾아라.

나쁜 수열은 인접한 두 개의 부분 수열이 동일한 수열이다. 그렇지 않으면 좋은 수열이다.

• 나쁜 수열 예 : 33, 32121323, 123123213
• 좋은 수열 예 : 2, 32, 32123, 1232123

 

 

 

 

 

1. 아이디어

1. 백트래킹으로 풀자.
   • N 범위가 1~80이라 넉넉해보이고, 중간에 가지치기 당할 것도 많아보였기 때문에 괜찮다고 보았다.
   • 사실 문제 분류를 보고 시작함 (엥?)
2. 기존 수열 + [1, 2, 3] 중 숫자 하나를 추가해서 다음 수열을 만든다. 길이 N이 될 때까지.
3. 숫자가 추가됐을 때 해당 수열이 좋은 수열인지 판단하기 위해 check_good 함수를 만든다.
   
   • 마지막 숫자를 더했을 때 그 순열이 좋은 순열인지 확인하려면, 마지막 숫자를 포함한 부분 수열이 동일한 지만 확인하면 된다.
   • 123 순열에 2를 추가해서 1232가 돼서 이것이 좋은 순열인지 확인하고 싶으면 끝에서부터 2, 32 만 확인하면 된다.
   • 마지막 숫자(2)를 포함하는 것만 확인해도 되는 이유는 이전에 들어온 수열(123)이 나쁜 수열이면 가지치기 당하기 때문에 마지막 숫자(2)를 더하는 과정 자체에 도달하지 못하기 때문이다.
4. 길이 N인 순열을 만들었으면 출력하고 그만둔다.
   • 첫 번째로 만나는 것이 가장 작은 수열이므로 바로 종료해도 된다.

 

 

 

 

2. 구현

def check_good(num):
    # -1 부터 -N//2까지 보면 됨 (그 이상은 길이 넘어가서 볼 필요 X) 
    for point in range(-1, -N//2 - 1, -1):
        # pattern이 동일하면 나쁜 수열
        pattern = num[point:]
        if num[point - len(pattern) : point] == pattern:
            return False
    # 끝날 때까지 걸리지 않으면 좋은 수열
    return True


def func(num):
    # 길이 N이면 그만두기
    if len(num) == N:
        print(num)
        exit()

    # 1, 2, 3 을 붙여서 순열 만들기 & 좋은 순열일 때만 재귀
    for i in ['1', '2', '3']:
        next_num = num + i
        if check_good(next_num):
            func(next_num)



N = int(input())
for j in ['1', '2', '3']:
    func(j)