[백준] 2661번 좋은수열 Python 해설 (백트래킹 알고리즘)

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

2661번: 좋은수열

백트래킹 알고리즘으로 분류된 문제이다.

코딩 테스트를 몇 차례 보면서 탐색, 백트래킹 쪽 문제에 약하다는 걸 알고 관련 문제를 많이 풀어보려고 하는 중이다.

 

풀이

---

입력받은 자릿수만큼의 길이가 될 때까지 깊이 우선 탐색을 진행하게 된다.

깊이 우선 탐색만 예를 들면 n = 7일 경우 첫 결과는 1111111이 된다. (최솟값 우선 조건 적용)

하지만 백트래킹 알고리즘을 적용하여 깊이 우선 탐색에 조건을 걸게 된다.

첫 번째 자리가 1이고 두 번째 자리가 1인 경우  나쁜 수열이 된다.

두 번째 자리에서 1을 선택하는 경우를 깊이 우선 탐색에서 제외한다면

1111111 ~ 121111111의 경우를 모두 제외시킬 수 있다.

내가 이해한 대로 설명하는 것도 참 어렵다...

 

for i in range(1, (idx//2) + 1):
    if s[-i:] == s[-2*i:-i]: return -1

위 코드는 선택한 수 (1, 2, 3 중 하나)가 적합한 수 인지를 판단하게 된다.

나쁜 수열인지 확인하는 과정이라고 생각하면 된다.

현재 체크 중인 자릿수 의 절반만큼만 반복하면 전체 수열에 대해 체크가 가능하다.

ex) 12131213의 경우 n = 8이고 마지막 자리 숫자를 선택할 때 네 개의 문자열을 묶어서 나쁜 수열인지 체크를 진행하면 나쁜 수열인지 좋은 수열인지 판단할 수 있다. (n//2 = 4)

 

- 정답 코드

def back_tracking(idx):
    for i in range(1, (idx//2) + 1):
        if s[-i:] == s[-2*i:-i]: return -1

    if idx == n:
        for i in range(n): print(s[i], end = '')
        return 0

    for i in range(1, 4):
        s.append(i)
        if back_tracking(idx + 1) == 0:
            return 0
        s.pop()

if __name__ == "__main__":
    n = int(input())
    s = []
    back_tracking(0)

 

 

결과

---

한 방에 통과했다.

알고리즘 문제 푸는 양은 줄었지만 실력은 줄지 않는다! (잘한다는 뜻은 아니다)