(미완)동적 계획법(다이나믹 프로그래밍, DP). 2

첫 글을 너무 대충 정리해서... 공부하다보니 다이나믹 프로그래밍의 엄청난 공부량을 느끼고 재정리. 

한개나 두개정도 글을 더 쓸수도 있을듯 싶다.

첫글 : http://qkqhxla1.tistory.com/585

다이나믹 프로그래밍의 프로그래밍 패턴.

1. 재귀적으로 짜는 패턴.

dp = [[-1 for j in xrange(10)] for i in xrange(10)] 

def function(a, b):

   if ~~~: return ~~~ #기저 사례. 미로찾기면 끝에 도달했다던가 하는등.

   

   ret = dp[a][b] #c++에서는 참조형으로 int& ret = dp[a][b];처럼 쓴다.

   if ret != -1: return ret #이미 a,b에 대한 값을 구한 적이 있으면 즉시 반환. 위에서 리스트 -1로 초기화.

   dp[a][b] = function(a+1, b) + function(a, b+1) #이런식으로 깊게 들어가기. 예시.

   return dp[a][b] #반환.

이런 패턴의 예. 위에 링크된 첫 글에서 짠 점프 문제. 

만드는 방법.

1. 완전 탐색 알고리즘으로 답을 반환하는 알고리즘을 설계.

2. 전체 답보다는 앞으로 남은 선택들에 대한 답을 반환하도록 변경.

3. 메모이제이션 활용. 이전에 이미 했다면 더 안한다던가.

좋은 문제 2.

원주율 외우기.

똑똑한 사람들이 원주율을 외우는 방법은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는 방법입니다.

각 조각들의 난이도가 아래와 같은때 최소의 난이도를 계산하는 프로그램을 작성하시오.

1. 모든 숫자가 같을때 ex)333, 55555 난이도 : 1

2. 숫자가 1씩 증가하거나 감소하는 등차수열일때 ex) 1234, 4321 난이도 : 2

3. 두 개의 숫자가 번갈아가며 나타날때 ex) 323, 54545 난이도 4

4. 숫자가 등차 수열을 이룰 때 ex)147, 8642 난이도 5

5. 이 외의 모든 경우 ex)17912, 331 난이도 10.

방법론.

첫번째 조각(길이 3~5) + 첫번째 3~5조각 빼고 나머지 수열에 대한 최적해 를 구한다.

# -*- encoding: cp949 -*-
INF = 99999999999
def classify(a, b):
    m = n[a:b+1] #m은 a~b사이의 조각.
    if m[0]*len(m)==m: #모두같으면 1 리턴
        return 1
    prog = True #등차수열인데
    for i in xrange(len(m)-1):
        if int(m[i+1])-int(m[i]) != int(m[1])-int(m[0]):
            prog = False
    if prog and abs(int(m[1])-int(m[0]))==1: #1씩 증가하거나 1씩 감소하는 등차수열이면 2리턴
        return 2
    alter = True
    for i in xrange(len(m)): #353, 6565같은 두개씩 반복이면 4 리턴.
        if m[i] !=m[i%2]:
            alter = False
    if alter: return 4
    if prog: return 5 #위의 경우가 아닌데 등차수열이면 5 리턴.
    return 10 #나머지는 10 리턴

def memorize(begin):
    if begin==len(n): #끝까지 가면 0 리턴.
        return 0
    ret = dp[begin]
    if ret != -1: return ret #계산한 적이 있으면 리턴
    dp[begin] = INF 
    for L in xrange(3,6): #조각은 3,4,5로 나눌 수 있음.
        if begin + L <= len(n): 
            dp[begin] = min(dp[begin], memorize(begin + L) + classify(begin, begin + L - 1)) #첫 3~5조각 + 나머지 조각의 최적해.
    return dp[begin]

for t in xrange(input()):
    n=raw_input()
    dp = [-1 for i in xrange(len(n))]
    print memorize(0)
    print dp