[ALGOSPOT][DP] PI

PI

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

<코드>

#include <stdio.h>
 
int a[10100];
 
int three(int num)
{
    int nando = 10;
    
        if (a[num - 2] == a[num - 1] && a[num - 1] == a[num])
            nando = 1;
        else if (a[num - 2] + 2 == a[num - 1] + 1 && a[num - 1] + 1 == a[num])
            nando = 2;
        else if (a[num - 2] == a[num - 1] + 1 && a[num - 1] + 1 == a[num] + 2)
            nando = 2;
        else if (a[num - 2] == a[num])
            nando = 4;
        else if (a[num - 2] - a[num - 1] == a[num - 1] - a[num])
            nando = 5;
    
    return nando;
}
 
int four(int num)
{
    int nando = 10;
    
        if (a[num - 3] == a[num - 2] && a[num - 2] == a[num - 1] && a[num - 1] == a[num])
            nando = 1;
        else if (a[num - 3] + 3 == a[num - 2] + 2 && a[num - 2] + 2 == a[num - 1] + 1 && a[num - 1] + 1 == a[num])
            nando = 2;
        else if (a[num - 3] == a[num - 2] + 1 && a[num - 2] + 1 == a[num - 1] + 2 && a[num - 1] + 2 == a[num] + 3)
            nando = 2;
        else if (a[num - 2] == a[num] && a[num - 3]==a[num-1])
            nando = 4;
        else if (a[num - 3] - a[num - 2] == a[num - 2] - a[num - 1] && a[num - 2] - a[num - 1] == a[num - 1] - a[num])
            nando = 5;
 
    return nando;
}
 
int five(int num)
{
    int nando = 10;
    
 
    if (a[num - 4] == a[num - 3] && a[num - 3] == a[num - 2] && a[num - 2] == a[num - 1] && a[num - 1] == a[num])
        nando = 1;
    else if (a[num - 4] + 3 == a[num - 3] + 2 && a[num - 3] + 3 == a[num - 2] + 2 && a[num - 2] + 2 == a[num - 1] + 1 && a[num - 1] + 1 == a[num])
        nando = 2;
    else if (a[num - 4] == a[num - 3] + 1 && a[num - 3] == a[num - 2] + 1 && a[num - 2] + 1 == a[num - 1] + 2 && a[num - 1] + 2 == a[num] + 3)
        nando = 2;
    else if (a[num - 4] == a[num] && a[num - 2] == a[num] && a[num - 3] == a[num - 1])
        nando = 4;
    else if (a[num - 4] - a[num - 3] == a[num - 3] - a[num - 2] && a[num - 3] - a[num - 2] == a[num - 2] - a[num - 1] && a[num - 2] - a[num - 1] == a[num - 1] - a[num])
        nando = 5;
 
    return nando;
}
 
int main(void){
    int testcase;
    char c[10100];
    scanf("%d", &testcase);
    while(testcase--){
        int dp[10100];
        int size = 0;
        scanf("%s", c);
 
        for (int i = 0; i < 10100; i++){
            if (c[i] == 0)
            {
                size = i;
                break;
            }
            a[i] = c[i] - '0';
        }
        dp[0] = dp[1] = 1000000;
        dp[2] = three(2);
        dp[3] = four(3);
        dp[4] = five(4);
        dp[5] = dp[2] + three(5);
        dp[6] = dp[2] + four(6) < dp[3] + three(6) ? dp[2] + four(6) : dp[3] + three(6);
        
        for (int i = 7; i < size; i++){
            int on, tw, th;
            int temp_result;
            on = dp[i - 3] + three(i);
            tw = dp[i - 4] + four(i);
            th = dp[i - 5] + five(i);
            
            temp_result = on < tw ? on : tw;
            temp_result = temp_result < th ? temp_result : th;
            dp[i] = temp_result;
        }
 
        printf("%d\n", dp[size - 1]);
    }
}

<문제 푼 요령>

 1. 이 문제는 DP 문제이다. 

 2. 여기서 중요한것은 역시나 점화식이다. 

 3. three 는 3개의 경우를 따져서 난이도를 출력하는 함수 four는 4개의 경우를 따져서 난이도를 출력하는 함수 five는 5개의 경우를 따져서 난이도를 출력하는 함수이다.

 4. 그래서 이 함수들을 이용해서 1차원 dp 테이블을 만들어서 구한다. 설명이 부족해서 그림으로 대체하겠다.

위의 그림처럼 끊임없이 앞에있는 값을 이용해서 현재의 최소값을 비교해서 구해주는 것이다.