DP

이전의 값을 재활용하는 알고리즘이라고 할 수 있다.

DP는 코드는 짧지만 점화식을 세우는 것이 어렵다. 점화식을 명확하게 세운 후 코드를 작성하는 것이 중요하다. 이전 값을 구하는 것이 필요하기 때문이다.

감이 안온다면 일단 해보면서, 하나씩 그려보면서 규칙을 찾아보자.

---

11726 2xn 타일링

문제 링크

문제 접근

• A1: 1 , A2: 2 , A3: 1+2
• An = A(n-1) + A(n-2)
• for 문으로 3 부터 N 까지 돌면서
• 이전값과 그 이전값을 더해서 저장한다.
• 매번 계산마다 10007 로 나누어준다. (문제의 조건)

전체 코드

#include<iostream>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    
    int dp[1004];
    dp[1]=1;
    dp[2]=2;
    for(int i=3; i<=n; i++){
    	dp[i]=dp[i-1]+dp[i-2];
        dp[i]%=10007; // 문제의 조건
    }
	cout<<dp[n];
    return 0;
}

---

17258 인기가 넘쳐흘러

문제 링크

#include<bits/stdc++.h> 
using namespace std;     
int n, m, k, t, a, b, cnt[301], dp[301][301];
vector<pair<int, int>> v; 
int go(int here, int num, int prev){
    if(here == v.size()) return 0; 
    if(dp[here][num]) return dp[here][num];

    int cost = max(0, t - v[here].second); 
    int real_cost = (prev >= cost) ? 0 : cost;  

    int & ret = dp[here][num]; 
    if(num - real_cost >= 0){
        return ret = max(go(here + 1, num - real_cost, cost)+ v[here].first, go(here + 1, num, 0));
    }else return ret = go(here + 1, num, 0);  
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    cin >> n >> m >> k >> t; 
    for(int j = 0; j < m; j++){
        cin >> a >> b; 
        for(int i = a; i < b; i++)cnt[i] = min(t, ++cnt[i]);
    }
    int temp = cnt[1]; 
    int _count = 1; 
    for(int i = 2; i <= n; i++){  
        if(temp != cnt[i]){ 
            v.push_back({_count, temp});  
            _count = 0; 
            temp = cnt[i];
        }
        _count++;
    }
    v.push_back({_count, temp});
//    for(pair<int ,int> a : v){
//    	cout << a.first << " : " << a.second << "\n";
//	}
    cout << go(0, k, 0) << "\n"; 
    return 0;   
}