백준 2661 - 좋은수열

🔐 백준 2661 - 좋은수열

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

🔑 풀이

입력이 1 이상 80 이하의 자연수이므로, 80자리 각각에 1, 2, 3 중 하나가 들어가는 경우는

대충 계산해보면 $ 3^N $ 의 연산 횟수가 사용될 것이다. 또한, 각각의 자리에 숫자를 집어넣을 때,

좋은 수열인지, 나쁜 수열인지를 검사해야 하므로, 연산 횟수는 더욱더 늘어날 것이다.

따라서, 백트래킹 기법을 사용하여 가지치기의 과정을 통해 연산 횟수를 줄여야 한다.

우선 숫자 1, 2, 3을 넣을 때마다 좋은 수열인지를 판별하기 위해서는 현재 k 자리 정수라고

가정했을 때, $ k \div 2 $ 번 수행해야 한다.

예를 들어, 현재 수가 12131이고, 6번째 자리에 2를 추가한다고 하면, 좋은 수열임을 확인하기

위해, 2와 1을 비교하고, 12와 13을 비교해야하며, 마지막으로 312와 121을 비교하는

3번의 과정을 거쳐야 한다.

위의 알고리즘을 코드로 적용시키면 이 문제를 해결할 수 있다.

🧩 코드