[백준] 2661 : 좋은 수열 / python

1. 문제 설명

2661번: 좋은수열

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

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

• 33
• 3323
• 2121
• 123123213

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

• 2
• 32
• 32123
• 1232123

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

 

입력

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

 

출력

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

 

예제 입력 1

7

예제 출력 1

1213121

 

2. 풀이 전 계획과 생각

• N → 수열의 길이

 

완전 탐색으로 접근해봤을 때, 3 ^ 80이다. 😱

⇒ 가장 작은 수를 나타내는 수열을 출력하면, 시간 초과가 나지 않을 것이다. 백트레킹으로 가자. ✂️

 

각 자리수 마다 1, 2, 3을 선택하자.

연속하는지 연속 안하는지 체크해주기 위해, 연속 부분 수열의 시작과 끝 인덱스를 설정하자.

연속하면, 나쁜 수열이다.

 

다 고르고 좋은 수열인지 아닌지 확인해주려고 했는데 그러면, 시간초과가 난다.

⇒ 중간에 연속하는 게 있다면 나쁜 수열이니 더이상 탐색하지 않도록 하자.

 

choose_num(curr_digit) : 현재 자릿수에서 1-3을 선택한다.

→ 종료조건 curr_digit > N

 

is_good() : 선택한 숫자가 연속하는지 체크해주는 함수

 

3. 풀이하면서 막혔던 점

is_good() : 선택한 숫자가 연속하는지 체크해주는 함수

 

🤔 선택한 숫자는 연속하는지 체크해주는 함수를 구현해주려면 어떻게 하면 좋을까?

partA의 start_index와 end_index를 설정해주고,

partB의 start_index와 end_index를 설정한다.

이 둘이 연속하는지 체크해준다.

 

def is_good():
# 가능한 연속 부분 수열의 길이 범위를 탐색한다.
    length = 1
    while True:
        # 연속 부분 수열의 시작과 끝 인덱스를 설정해준다.
        start1, end1 = len(choose) - length, len(choose) - 1
        start2, end2 = start1 - length, start1 - 1

        if start2 < 0:
            break

        # 인접한 연속 부분 수열이 같은지 여부를 확인한다.
        if choose[start1:end1 + 1] == choose[start2:end2 + 1]:
            return False

        length += 1
    
    return True

 

4. 풀이

import sys
N = int(input())
choose = []
numbers = [1, 2, 3]

def is_good():
    length = 1
    while True:
        start1, end1 = len(choose) - length, len(choose) - 1
        start2, end2 = start1 - length, start1 - 1

        if start2 < 0:
            break

        if choose[start1:end1 + 1] == choose[start2:end2 + 1]:
            return False

        length += 1

    return True

def choose_num(curr_digit):
    if curr_digit > N:
        for element in choose:
            print(element, end="")
        sys.exit(0)

    for num in numbers:
        choose.append(num)
        if is_good():
            choose_num(curr_digit + 1)
        choose.pop()

choose_num(1)

 

5. 풀이 후 알게된 개념과 소감

• 위의 경우는 길이가 80이므로, 마지막까지 다 선택해서 확인하면 시간초과가 난다.
  그러므로, 중간에 확인해서 아닌 경우는 가지치기 함으로 풀자.
• 숫자가 크면, 완탐, 또는 중간에 가지치기 할 경우가 있는지 확인하자.