[Python][백준] 2661. 좋은수열 / 백트래킹 (G4)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

N = int(input())

def check(lst):
    for i in range(1,len(lst)//2+1): # 몇 개씩 확인 할 것인지
        for j in range(len(lst)-i):
            if lst[j:j+i] == lst[j+i:j+i+i]:
                return False
    return True           

mn = 1e100
def dfs(n,lst):

    # return -1로 상위 호출에서 다른 경로 탐색 제어
    if not(check(lst)):
        return -1
    
    global mn
    if n == N:
        lst = list(map(str,lst))
        mn = min(int("".join(lst)),mn)
        return 0
    
    for i in range(1,4):
        lst.append(i)
        if dfs(n+1,lst) == 0:
            return 0
        lst.pop()

dfs(0,[])
print(mn)

 

1. dfs에서 백트래킹 응용 문제로, 다소 복잡한 조건들이 있다.

 

2. 먼저 수열들이 "나쁜 수열"인지 "좋은 수열"인지를 파악해야한다.

이를 위한 check 함수를 만들어 준다. 

for i in range(len(lst)-1):
	print(lst[i:i+2],lst[i+2:i+2+2])

처음부터  바로 check 함수를 구현하기는 어렵기 때문에,

먼저 간단한 for문으로 테스트를 해본다. 

(해당 for문은 2개씩 비교를 할 때의 예시이다.)

 

3. N의 범위가 80까지이므로, 가지치기를 잘 해줘야 한다.

CASE 1) 재귀함수를 실행할때 check 함수의 return이 False인 경우, 해당 재귀함수의 return을 -1로 하여 더 이상 상위 호출 탐색을 하지 않는다.

CASE 2) 가장 최소값을 찾는 것이기 때문에, 모든 조건을 만족하는 lst를 다 구할 필요가 없다.  재귀함수 특성상 가장 빨리 조건에 만족하는 수가 가장 작은 값이 된다. 
(재귀함수 for문의 return 0으로 연쇄적으로 재귀함수들이 종료된다. )

 

이 두가지의 가지치기로 시간 초과를 막을 수 있다. 

 

 

📌  문제 코멘트

check 함수 부분 구현이 좀 어려웠다. 

먼저 경우의 수를 쪼개주고 하나 하나 구현해보자. 

 

위의 문제 같은 경우, 이렇게 두가지 경우로 나눌 수 있다.

- 1개가 같은경우 / 2개가 같은 경우 / 3개가 같은경우 ... 

- [~:1] ~[1:~]...  

 

그리고 이 경우들을 한번에 작성하지말고,

간단한 for문 예시로 작성하면 좀 더 수월하게 가능하다.

 

또 어려웠던거는 단순 재귀함수가 아니라, 가지치기들 조건들이였다.

특히, return -1을 쓰는 것은 이번이 처음이었다. 

그리고 재귀함수 for 문에 return 0을 활용한것도 처음이다. 

 

확실히 골드 문제는 조건들이 많은거 같다. 

---

📚문제

숫자 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

예제 출력 1 복사

1213121