[BOJ]14501号-退社

💎 最初の開発投稿🎉🎉

3年次の2学期の冬休みから新しい開発が始まり、今後のアルゴリズムの問題や、先端開発者として使用されるフレームワークや問題点などを開発中に記録してまとめるようになりました.

今、私のバックグラウンドの提詞はSilver 1で、主にSilver 3からGold 3の間の問題を解決して、どこが私が脆弱で解決しにくいのか、あるいはどの方法が他の小さなシールを得ることができるのか、コードテストの準備を通じて記録することが役に立つと思います.

不足点が多いので、簡単な問題から、どのようなタイプの問題があるかを記録し、開発中に作成し続け、私に役立つことを期待しています.

💎 質問する
コンサルタントの白俊さんが会社を辞めます.
今日からN+1日で辞めるために、残りのN日にできるだけ多くの相談をします.
白俊は秘書にできるだけ多くの相談を依頼し、秘書は1日に1回異なる人に相談を手配した.
各コンサルティングは,コンサルティングを完了するのに要する時間内にTIとコンサルティングを行う際に得られる金額Piからなる.
N=7の場合は、以下のコンサルティングスケジュールを参照してください.
1日2日3日4日5日6日7日
1日のカウンセリングは全部で3日かかりますが、カウンセリング時にもらえる金額は10です.5日間のお問い合わせは2日間かかりますが、受け付けられる金額は15です.
相談にかかる時間は1日以上かかる場合がありますので、すべての相談はできません.例えば、1日に問い合わせを行った場合、2日、3日に問い合わせをすることはできません.2日に問い合わせをすれば、3、4、5、6日には問い合わせができない.
なお、N+1日は会社にいないため、6,7日は相談できません.
退職前にカウンセリングを行う最大の利益は1日、4日、5日にカウンセリングを行うことであり、その際の利益は10+20+15=45である.
商談がうまくいけば、白俊に最大の収益をもたらす計画を立ててください.
💎 入力
第1行はN(1≦N≦15)を与える.
2行目からN行目まで、TIとPiはスペースで区切られ、1日からN日まで順次与えられる.(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
💎 しゅつりょく
1行目は白俊が得られる最大の利益を出力する.
💎 解答方法
Dinamicプログラミングで解決できます.
私は主にベクトルを用いて配列に関する問題や情報(サイズの調整が容易であるため)を格納し,ベクトルを用いてdpの初期値と解題をどのように設定するかを考えた.
この問題では,N日間の時間帯があれば最大収益を求めるために商談を行う必要があるため,これまで求めた最大収益と現在求めたdp値に新たに増加した商談収益を比較することができる.
トップダウン法を用いてN日から順次dpを解くと,単O(n)回の時間複雑度を求めることができるので効率的であり,N日のdpから1日のdpまでの方法を利用した.

for(int i = N; i >= 1; i--){
    if(i + T[i] - 1 > N){
        dp[i] = dp[i + 1];
        continue;
    }
    dp[i] = max(dp[i + T[i]] + P[i], dp[i+1]);
}

以上のように,現在求められているN日目の相談の相談期間を完了するには,1日の相談期間が必要である.したがって、i+T[i]−1からN日間の問合せ時間と現在検査されている問合せ日iを減算し、実行する必要がある1日を減算して問合せ時間全体のN日間より大きくすると、実行できない問合せであるため、前のdpの値をそのまま加算して変化がないことを示す.
可能なコンサルティングであれば、前のdpの値と大きさを比較し、より大きな収益を現在のdpの値に格納する必要がある.これは、前にdpを計算した値、すなわち実行可能なコンサルティングの延長線であるため、dp[i+T[i]+P[i]の収益を増やす必要がある.当日のdpの値には,現在求められている問い合わせ日の収益の値を加える.したがって,このdpと以降のdp値を比較し,より大きなものを現在のdpに記憶すればよい.
💎 完全なコード

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> T(16);
vector <int> P(16);
vector <int> dp(16);

int main(int argc, const char * argv[]) {
    int N;
    int tmp1,tmp2;
    cin >> N;
    
    for(int i = 1;i <= N;i++){
        cin >> tmp1 >> tmp2;
        T[i] = tmp1;
        P[i] = tmp2;
    }
    for(int i = N; i >= 1; i--){
        if(i + T[i] - 1 > N){
            dp[i] = dp[i + 1];
            continue;
        }
        dp[i] = max(dp[i + T[i]] + P[i], dp[i+1]);
    }
    
    cout << dp[1] << "\n";
    
    return 0;
}

💎 悶える
これは確かにdp問題の解が最も多く,時間が長ければ解決できるという考え方であるが,初期値を素早くどのように入れるかは時間的に複雑度が高いため,導出過程によっては解決しにくい可能性がある.dp問題の解題方法はいろいろな助けがあるので、手でルールを模索する方法が第一に、うまくいかなかったら、まず前と後の値を利用して解決しているかどうかを確認し、近づくと逆に解決しやすい場合が多いので、必ず多めに解かなければなりません.これはダイナミックプランニングで解決している問題です.
がんばってください.