[白駿12852-1製作2]

##問題分析

DP

DP問題における基本問題

時間の複雑さ

インプリメンテーション

テーブル定義、ポイント定義、初期値設定については、問題を以前の解の1に設定するのと同様です.
検索パス

int R[1000002];
// R[i] 의 원소가 K 라면 : i에서 K로 가는 것이 최적이라는 의미이다.

for(int i = 3; i <= N; i++){

        // 1로 뺀 값
        T[i] = T[i-1] + 1;
        R[i] = i-1;

        // 3으로 뺀 값
        if(((i % 3) == 0) && T[i/3] + 1 < T[i]){
            T[i] = T[i/3] + 1;
            R[i] = i/3;
        }

        // 2로 뺀 값
        if(((i % 2) == 0) && T[i/2] + 1 < T[i]){
            T[i] = T[i/2] + 1;
            R[i] = i/2;
        }
        
    }

上記のコードに示すように、T[K]は、T[K-1]、T[k/2]、T[k/3]のうち、どこに行くのが最適かを判断し、対応する値R[K-1]、R[k/2、R[k/3]も値を変更する必要がある.
あとで

while(true){
        cout << cur << " ";
        if(cur == 1) break;
        cur = R[cur];
}

パスを追跡するには、次のコードを使用します.

さまよう部分

R配列の場合、初期値設定エラーにより無限ループに陥る.

取得する

学習DPタイプ-パスの検索

フルコード[マイコード]

#include <iostream>
using namespace std;

int T[1000002]; // 1-indexed
int R[1000002]; // 1-indexed

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

int N;

void get_input(){
    cin >> N;
}

void print_board(){
    for(int i = 1; i <= N; i++){
        cout << "i : " << i << " ";
        cout << R[i] << " ";
    }
    cout << "\n";
}


int main(void){
    init();
    get_input();

    // 초기값 설정
    T[1] = 0;
    T[2] = 1;
    R[1] = 0;
    R[2] = 1;

    for(int i = 3; i <= N; i++){

        // 1로 뺀 값
        T[i] = T[i-1] + 1;
        R[i] = i-1;

        // 3으로 뺀 값
        if(((i % 3) == 0) && T[i/3] + 1 < T[i]){
            T[i] = T[i/3] + 1;
            R[i] = i/3;
        }

        // 2로 뺀 값
        if(((i % 2) == 0) && T[i/2] + 1 < T[i]){
            T[i] = T[i/2] + 1;
            R[i] = i/2;
        }
    }

    int cur = N;

    // print_board();

    cout << T[N] << "\n";

    while(true){
        cout << cur << " ";
        if(cur == 1) break;
        cur = R[cur];
    }
    cout << "\n";

    return 0;
}

に感銘を与える

定義

表

点火式誘導

設定

初期値

3つの過程で問題を解決することを知っていても、実際に問題を解決するには多くの経験が必要らしい.最終的には多くの問題を解決してこそ答えがあるようだ.

リファレンス

YouTubeで
動画リスト
かなりすっきり整理されていてわかりやすいです.