[ BOJ / 파이썬 ] 2661 좋은 수열

백트래킹 부분 연습 중이다.

 

대충 함수 구성은 하는데 제일 중요한 백트래킹 부분 자체를 계속 버벅인다.

 

판별식 + 어떻게 이전 단계로 돌아갈 지 계속 생각 중.

 

해당 링크의 작성자 분의 코드가 내 아이디어에 가장 유사한 구현이었다.

부럽습니다. ㅎㅎ..

https://sungmin-joo.tistory.com/66

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

 

 

이분 풀이가 다음에 비슷한 유형 나왔을 때 생각해내기 더 쉬울 것 같다.

https://donghak-dev.tistory.com/180

[알고리즘][Python] 백준 좋은수열 2661 문제 풀이

 

해당 문제에서 구현or생각해야할 파트는 3가지로 나뉜다.

 

1. 전체 함수 구성

: 인자 정의, 기본 종료 조건

2. 백트래킹 판별 여부 시 동작

3. 판별식 설계 및 구현

 

나는 1번은 해낸 것 같다.

2번은 절반, 3번은 아이디어만 떠올리고 구현에서 실패했다. 

 

다시 이해를 위해 풀어서 보자면

인자: 현재까지의 좋은 수열, n
함수 ( 현재 받아온 수열 ):
    만약 "받아온 수열을 체크"했는데 "실패"라면,
        이 함수는 종료(리턴)    # 이게 백트래킹에 해당함. 조건에 안 맞으면 돌아갓! 느낌
    만약 "받아온 수열 길이"가 n과 같으면:
        그 숫자 출력    // 문제에서 제시한 종료조건이므로 종료,(*)
        최종종료
    그거 아니면,
        // 주어진 옵션대로 모두 뻗어나가며 계산해보기
        업뎃 숫자는 1 ~ 3 까지 
            함수( 현재 받아온 수열에서 업뎃숫자를 더한 수열,  n) //(**)

n 받아서
함수( 빈 문자열, n ) // 첫 호출

(*) : 굳이 최솟값을 찾는 과정 없이 끝내는 이유는 이미 아래에서 업뎃할 때, 1, 2, 3 크기 순으로 붙여나가기 때문에 제일 먼저 종료조건 충족하는게 제일 작은게 보장되어 있음.

(**): 일단 업뎃해서 넘기면 걔가 맞는지는 다음 과정에서 체크하고 돌려보내던 계속 내려가던 함.

 

흐.. 백트래킹 혼자 풀 수 있을까..? 계속 부딪혀보자.