[알고스팟] 원주율 외우기 - 동적 계획, 최적 부분 구조

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

원주율 외우기(링크)

먼저 완전 탐색의 방식으로 생각해보면 3개, 4개, 5개로 나눌 수 있는 모든 경우에 대해 나눠진 조각의 난이도를 계산하고 이를 비교해 가장 낮은 결과를 선택한다.

 

직관적으로 최적 부분 구조가 성립함을 알 수 있다. 어떤 위치에 있던지 남은 숫자들에 대해서는 가장 낮은 난이도 점수를 받을 수 있도록 나누어야 한다. (그 이전 수들은 어떻게 나누었는지 고려할 필요 없다.)

 

그러므로 현재 작업 중인 조각에 대해 계산한 난이도 점수와 재귀 호출할 다음 작업 조각의 점수를 더해 반환하는 방식으로 부분 문제를 정의한다.

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int INF = 987654321;
int cache[10000];
vector<int> numbers;

int calculateLevel(vector<int>& piece) {
    int first = piece[0], second = piece[1];
    int len = piece.size();

    // Level 1 : All same.
    bool isCorrect = true;
    for (int i = 1; i < len; ++i) 
        if (piece[i] != first) isCorrect = false;
    if (isCorrect) return 1;
    
    // Level 2 : Increase or decrease by 1.
    isCorrect = true;
    if (first + 1 == second) {
        for (int i = 1; i < len - 1; ++i) 
            if (piece[i] + 1 != piece[i + 1]) isCorrect = false;
    }
    else if(first - 1 == second) {
        for (int i = 1; i < len - 1; ++i) 
            if (piece[i] - 1 != piece[i + 1]) isCorrect = false;
    }
    else isCorrect = false;
    if (isCorrect) return 2;

    // Level 4 : Two numbers are repeating.
    isCorrect = true;
    for (int i = 2; i < len; ++i) {
        if (i % 2 == 0 && piece[i] != first ||
                i % 2 == 1 && piece[i] != second)
            isCorrect = false;
    }
    if (isCorrect) return 4;

    // Level 5 : Isometric sequence.
    isCorrect = true;
    int diff = first - second;
    for (int i = 1; i < len - 1; ++i) 
        if (piece[i] - piece[i + 1] != diff) isCorrect = false;
    if (isCorrect) return 5;

    return 10;
}

int PI(int idx) {
    // Base case: If you get to the end, return.
    if (idx == numbers.size()) return 0;

    int& ret = cache[idx];
    if (ret != -1) return ret;

    ret = INF;
    // Task piece: Take 3 to 5 steps from current index.
    for (int step = 3; step <= 5; ++step) {
        if (idx + step <= numbers.size()) {
            vector<int> piece;
            for (int i = idx; i < idx + step; ++i) piece.push_back(numbers[i]);
            ret = min(ret, PI(idx + step) + calculateLevel(piece));
        }
    }
    return ret;
}

int main() {
    int C; cin >> C;
    vector<int> answers;
    string str;
     
    while (C-- > 0) {
        memset(cache, -1, sizeof(cache));

        cin >> str;
        for (int i = 0; i < str.size(); ++i) 
            numbers.push_back(str[i]-'0');
        
        answers.push_back(PI(0));
        numbers.clear();
    }

    for (const auto& e: answers) cout << e << endl;

    return 0;
}