c++) 8장 - 원주율 외우기 (dp)

문제 : algospot.com :: PI

algospot.com :: PI

 

풀이과정

1. 조각의 길이가 3,4,5로 나뉘어질 수 있기 때문에, 난이도가 가장 낮은 경우의 수는

 

※ 길이가 3인 조각의 난이도 + 3글자를 제외한 나머지 수열에 대한 최소난이도

※ 길이가 4인 조각의 난이도 + 4글자를 제외한 나머지 수열에 대한 최소난이도

※ 길이가 5인 조각의 난이도 + 5글자를 제외한 나머지 수열에 대한 최소난이도

이렇게 3가지 경우가 있기 때문에 for문은 최대 3번씩 돌아가게 된다.

 

2. 난이도 조건에 맞게 값을 리턴해주는 함수를 따로 만들어서 점화식에 추가해주면,

점화식은 L=3,4,5일때 {start~start+L-1에 대한 난이도} + {start+L에서 시작하는 최소 난이도}

이렇게 정할 수 있다.

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int C,piSize;
int pi[10001];
int cache[10001];

int calculate(int s, int e) {
    int complete = true;
    // 모든 숫자가 같은지 체크
    for(int i=s; i<e; i++) {
        if(pi[i] != pi[i+1]) {
            complete = false;
            break;
        }
    }
    if(complete) return 1;
    complete = true;

    // 등차수열인지 체크
    for(int i=s; i<e-1; i++) {
        if(pi[i] - pi[i+1] != pi[i+1] - pi[i+2]) {
            complete = false;
            break;
        }
    }
    if(complete && (pi[s] - pi[s+1] == 1 || pi[s+1] - pi[s] == 1))
        return 2;
    else if(complete)
        return 5;

    complete = true;

    // 번갈아가면서 나타나는지 체크
    int prev = pi[s];
    int next = pi[s+1];
    for(int i=s; i<=e; i+=2) {
        if(prev != pi[i]) {
            complete = false;
            break;
        }
    }
    if(complete == false) return 10;
    for(int i=s+1; i<=e; i+=2) {
        if(next != pi[i]) {
            complete = false;
            break;
        }
    }
    if(complete == false) return 10;
    return 4;
}

int memorize(int start) {
    // 기저사례 : 끝에 도달
    if(start == piSize) return 0;

    int &ret = cache[start];
    if(ret != -1) return ret;
    ret = INF;
    for(int L=3; L<=5; L++) {
        if(start+L <= piSize) {
// 점화식 : {start~start+L까지 난이도} + {start+L 이후부터의 최소난이도}
            ret = min(ret, calculate(start,start+L-1)+memorize(start+L));
        }
    }
    return ret;
}

int main()
{
    string s;
    scanf("%d",&C);
    for(int c=0; c<C; c++) {
        memset(cache,-1,sizeof(cache));
        cin >> s;
        piSize = s.size();
        for(int i=0; i<s.size(); i++) {
            pi[i] = s[i]-48;
        }
        printf("%d\n",memorize(0));
    }
}