[2w] DP(Dynamic Programming)

Dynamic Programming

DP 공부자료 : reference
백준 1446

#include <iostream>
#include <vector>
using namespace std;
int N,D;
struct Road{
    int start, end, len;
};
int main(){
    cin>>N>>D;
    vector<Road> rV;
    vector<int> dp(D+1);
    for(int i=0;i<N;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c>=(b-a)) continue;
        Road road;
        road.start=a;
        road.end=b;
        road.len=c;
        rV.push_back(road);
    }
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=D;i++){
        dp[i]=dp[i-1]+1;
        for(int j=0;j<rV.size();j++){
            if(i==rV[j].end){
                int compLen=dp[rV[j].start]+rV[j].len;
                if((dp[i])>compLen) dp[i]=compLen;  //같은 도착지로 지름길이 여러개일수 있으므로 전부 탐색
            }
        }
    }
    cout<<dp[D];
    return 0;
}

백준 15989
//아이디어

코드

#include <iostream>
#include <vector>
int dp[10001];
using namespace std;
int N;
int alphaCount(int n){
    int cnt=0;
    for(int i=0;i<=(n/3);i++){
        int nMinusThree=n-(3*i);
        if (nMinusThree%2==0) cnt++;
    }
    return cnt;
}
int main(){
    cin>>N;
    vector<int> input(N);
    dp[1]=1;
    int maxN=0;
    for(int i=0;i<N;i++){
        cin>>input[i];
        if(maxN<input[i]) maxN=input[i];
    }
    for(int i=2;i<=maxN;i++) dp[i]=dp[i-1]+alphaCount(i);
    for(int i=0;i<N;i++) cout<<dp[input[i]]<<"\n";
    return 0;
}