DP(4) - 카드 구매하기, 오르막 수, 스티커

 

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

D[n]을 카드 n개를 구매하기 위해 지불해야 하는 최댓값으로 지정했는데 그 뒤로 어떻게 해야 할지 모르겠었다. 

 

D[n]의 초기값은 입력한 값임

D[2] = D[1]+D[1] or D[1];

D[3] = D[1]+D[2] or D[3];

D[4] = D[1]+D[3] or D[2]+D[2] or D[3]+D[1] or D[4];

 

테이블 설정만 해놓고 막막했는데 이렇게 아래서부터 천천히 올라가면 D[4]=D[1]+D[1]+D[1]+D[1] 이런 식으로 바꿀 필요가 없이 D 두 개의 합으로 나타낼 수 있다.

#include <bits/stdc++.h>
using namespace std;
int d[1005]; //D[n] 카드 n개를 구매하기 위해 지불해야 하는 최댓값
int main(){
	ios::sync_with_stdio(0); 
	cin.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>d[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			d[i]=max(d[i-j]+d[j],d[i]);
		}
	}
	cout<<d[n];
	return 0;
}

---

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

D[i][j] 길이 i에 j로 끝나는 오르막 수의 수

D[1][0~9] = {1,1,1,1,1,1,1,1,1,1}

D[2][0~9] = {1,2,3,4,5,6,7,8,9,10}

D[3] 부터는 머리속으로 생각하기 복잡해진다.

 

규칙을 찾아보자.

D[3][0] = D[2][0]

D[3][1] = D[3][0] + D[2][1]

D[3][2] = D[3][0] + D[2][1] + D[2][2]... 

규칙을 찾았다.

D[i][j] = D[i][j-1] + D[i-1][j]

#include <bits/stdc++.h>
using namespace std;
int d[1003][10];
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		d[i][0]=1;
		for(int j=1;j<=9;j++){
			d[i][j]=d[i][j-1]+d[i-1][j];
			d[i][j]%=10007;
		}
	}
	cout<<accumulate(d[n],d[n]+10,0)%10007;
	return 0;
}

accumulate는 누적합을 구하는 함수이고, 두 번째 인자는 미만인 값이다.

---

https://www.acmicpc.net/problem/9465

9465번: 스티커

DP... 정말 쉽지 않다.

#include <bits/stdc++.h>
using namespace std;
int d[5][100003], a[5][100003];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin>>t;
    while(t--){
        int n; cin>>n;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        d[1][1]=a[1][1]; d[2][1]=a[2][1];
        d[1][2]=a[1][2]+d[2][1];
        d[2][2]=a[2][2]+d[1][1];
        for(int i=3;i<=n;i++){
            d[1][i]=a[1][i]+max(d[2][i-2],d[2][i-1]);
            d[2][i]=a[2][i]+max(d[1][i-2],d[1][i-1]);
        }
        cout<<max(d[1][n],d[2][n])<<'\n';
    }
    return 0;
}