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

8.7 문제: 원주율 외우기 (문제 ID: PI, 난이도 : 하)

 

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

algospot.com :: PI

 

컨셉

3~5자리씩 끊어 읽는 점화식을 세워봤다.

int pi(int begin, int end)  // [begin,end)까지 읽는 최소 난이도

pi(begin, end) = min( pi(begin, begin+3), pi(begin, begin+4), pi (begin, begin+5) ) + level(begin, begin + n)

 

초안

위의 점화식을 이용했다. 다만, end는 처음부터 끝까지 동일했기 때문에 파라미터에서 빼 버렸다. begin만 이용했다.

 

내가 쓴 코드 (정답, 148ms)

/**
 * @name    8.7. 원주율 외우기
 * @ID      PI
 * @date    2019-08-06
 * @author  Sunmon
 */

#include <iostream>
#include <cstring>
#define MIN(a,b)  (a<b? a: b)
using namespace std;

const int INF = 987654321;
string str;

//str[begin,end)의 레벨 리턴
int level(int begin, int end)
{
    //숫자 조각을 가져온다
    string s = str.substr(begin, end-begin);
    
    //모두 같은 경우
    //s첫글자로 s와 같은 길이의 문자열을 생성해서 s와 비교
    if(s == string(s.length(), s[0])) return 1;

    //등차수열인지 검사
    int diff = s[1] - s[0]; //공차
    bool seq = true;       //등차수열 여부
    for(int i = 1; i< end- begin; i++)
    {
        if(s[i]-s[i-1] == diff) continue;
        seq = false;
        break;
    }

    //등차수열이면 공차에 따라 난이도 리턴
    if(seq)
    {
        if(diff == -1 || diff == 1) return 2;
        else return 5;
    }

    //숫자 번갈아 나타나는지 검사
    bool twin = true;
    for(int i = 0; i< end- begin; i++)
    {
        if(s[i] == s[i%2]) continue;
        twin = false;
        break;
    }

    //숫자 번갈아가면 4리턴, 아니면 그냥 10 리턴
    if(twin) return 4;
    return 10;
}


int cache[10000+2];
//str을 begin부터 검사했을 때 최소 난이도 합 리턴
int pi(int begin)
{
    //base case: 끝까지 다 돈 경우
    if(begin == str.length()) return 0;
    
    int& ret = cache[begin];
    if(ret != -1) return ret;
    ret = INF;

    for(int i = 3; i<=5; i++)
    {
        if(begin + i > str.length()) break;
        ret = MIN(ret, level(begin, begin+i) + pi(begin + i));
    }

    return ret;
}

int main()
{
    int C;
    cin >> C;
    while( C--)
    {
        memset(cache, -1, sizeof(cache));
        cin >> str;
        cout << pi(0) << endl;
    }
}

 

주의

string s = string(6, 'f');  // s = ffffff. 글자수만큼 해당 글자로 구성된 문자열 생성