[알고리즘] BOJ 2661 좋은 수열 #Python

[BOJ] 2661 좋은 수열 바로가기

📍 문제

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

---

📍 풀이

🧷 풀이 과정

BFS

def dfs(sequence):
    if N == len(sequence):
        print(sequence)
        exit()
    for i in range(1, 4):
        if checkSymmetry(sequence+str(i)):
            dfs(sequence+str(i))

• 수열(sequence)의 길이가 입력받은 숫자(N)와 같다면 해당 수열을 출력하고 프로그램을 종료(exit())한다.
• 만약 수열의 길이가 입력받은 숫자보다 작다면 현재 수열(sequence)에 숫자 1, 2, 3 을 연결한 값을 대칭이 발생하는지 확인하는 함수인 checkSymmetry()를 이용하여 나쁜 수열을 찾아낸다.

대칭 확인

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

• 파라미터로 전달받은 수열(sequence)의 값에서 발생할 수 있는 모든 대칭 성분을 조사하여 대칭이 발생하는지 확인한다.
• 만약 조사 과정 중 대칭이 존재한다면 False 를 반환하고 대칭이 존재하지 않는다면 True를 반환한다.

✍ 전체 코드

# BOJ 2661 좋은수열
# https://www.acmicpc.net/problem/2661

from sys import stdin

def dfs(sequence):
    if N == len(sequence):
        print(sequence)
        exit()
    for i in range(1, 4):
        if checkSymmetry(sequence+str(i)):
            dfs(sequence+str(i))
    
def checkSymmetry(sequence):
    for i in range(1, len(sequence)//2+1):
        if sequence[-2*i:-i] == sequence[-i:]:
            return False
    return True

N = int(stdin.readline())
dfs('1')