[algospot][PI] 원주율 외우기

문제 : https://algospot.com/judge/problem/read/PI

---

DP 문제로 풀었다.

dp[ind] = 문자열[ind~끝]으로 구할 수 있는 최소 난이도.
        = 최소값(문자열[ind~ind+len)의 난이도 + dp[ind+len]) (3 <= len <= 5) 

점화식은 위와 같다.

 

레벨을 구하는 방법은 일단 문자 3개로 모든 숫자가 같은 경우(난이도 1), 숫자가 1씩 단조 증가나 감소하는 경우(난이도 2), 등차 수열인지(난이도 5)를 구분할 수 있다.

그리고 모든 문자열을 돌면서 구한 난이도가 유지되는지 판단 후 난이도가 변하지 않는다면 해당 난이도가 조각의 난이도가 된다. 만약 난이도가 변한다면 두 개의 숫자가 번갈아 출현하는지(난이도 4) 판단 후 그렇다면 난이도 4, 그렇지 않다면 난이도 10이 된다.

 

시간복잡도는 O(N) = O(|문자열|).

---

소스코드 : https://gist.github.com/fpdjsns/5bcf6be23a70d174959ad9562d01cdeb