[동적 계획법] PI 원주율 외우기

1. 완전 탐색 알고리즘

 

이 문제는 주어진 문자열을 3-5글자씩 끊어서

특정 규칙에의해 정해진 난이도를 부여하여

전체 문자열의 최저 난이도를 계산하는 문제이다.

 

이 문제를 풀 함수는

한번 호출되었을 떄 문자열을

3-5길이의 문자열과 나머지 문자열로 분할한다.

 

난이도 판별함수를 실행하여 문제를 해결하고 (최대 5번의 for문)

 

나머지 문자열은 재귀호출하여 다음 부분문제로 넘어간다.

 

이 함수는 문자열의 길이가 n일 떄

최소 n/3 의 깊이와 최대 n/5 깊이를 가지고

3^n/3 > leaf > 3^n/5 인 잎의 개수를 가진다.

 

따라서 완전 탐색은 지수적 수행 시간을 가지며

이는 시간초과를 의미한다.

 

2. 메모이제이션 적용

부분문제는 동일하다 i 이전과 i 이후

 

i의 이전 문자열은 i 이후 문자열을 해결하는데 아무 상관이 없기 때문에

 

이 문제는 최적 부분 구조가 성립한다.

 

왼쪽 문자열을 끊고나서 나머지 문자열의 시작을 i라고할때

 

cache[i] = i 에서 시작하는 문자열의 최저 난이도  

 

이 배열을 통해 각 부분문제를 최적으로 풀어서 전체 문제의 최적해를 구할 수 있다.

 

따라서 함수에 i 이후의 최저 난이도 를 반환하도록 구현했다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
//3 ~ 5
//min difficulty
// all same = 1
// nomal increase, nomal decrease = 2
// Alternately appear = 4
// isometric sequence = 5
// else  =  10
// cant 1234567
 
int diff[7] = {1, 2, 2, 4, 5, 10, 1234567};
int cache[10000];
 
int difficulty(const std::string &str)
{
    int state[5] = {
        0, 0, 0, 1, 1
    };
    char before = str[0];
    char bbefore = 0;
    int sub = 0;
    int beforeSub = 0;
    
    for(int i =  1; i <str.size(); i++)
    {
        sub = before - str[i];
        if(before == str[i])
            state[0]++;
        else if(before + 1 == str[i])
            state[1]++;
        else if(before - 1 == str[i])
            state[2]++;
        else if(i != 1 && sub == beforeSub)
            state[4]++;
        if(i != 1 && bbefore == str[i])
            state[3]++;
        
        beforeSub = sub;
        bbefore = before;    
        before = str[i];
    }
    for(int i = 0; i < 5; i++)
        if(state[i] == str.size() -1)
            return diff[i];
    return diff[5];
}
 
int pi(const std::string& str, int index)
{
    std::string tmpstr, nextstr;
    int &ret = cache[index];
    
    if(str.size() == 0) return ret = 0;
    if(str.size() < 3) return ret = diff[6];
    if(ret != -1) return ret;
    
    ret = diff[6];
 
    for(int i = 3; i <= 5 && i <= str.size(); i++)
    {
        tmpstr = str.substr(0,i);
        nextstr = str.substr(i);
        ret = std::min<int>(difficulty(tmpstr) + pi(nextstr, i + index)
                            , ret); 
    }
 
    return ret;
}
 
int main()
{
    int testCase = 0;
    std::string str = "";
    std::cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        memset(cache, -1, sizeof cache);
        std::cin>>str;
        std::cout<<pi(str, 0)<<std::endl;
    }
 
}

 

 

3. 시간 복잡도

 

이 문제는 최대 n 개의 부분 문제가 있고  각 부분 문제를 푸는데에는 상수항의 시간이 걸리므로

O(n)이다. 하지만 이 시간 복잡도는 인덱스로 부분문제로 나눌 때이다 위 함수는 substring을 사용했으므로

시간복잡도는 더 클것이다.

 

 

PI