dp연습1

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

9465번: 스티커

0	1	2	3	4	...	n
1	스티커[1][1]	스티커[2][1]	...	...	...	...
2	스티커[1][2]	스티커[2][2]	...	...	...	...

세로로 쭉 테이블 채우기 

dp[i][1] : 2번을 포기 1번 선택했을 때 최댓값

dp[i][2] : 1번을 포기 2번 선택했을 때 최댓값

dp[i][1] = max(dp[i-1][2] + A[i][1], dp[i-1][1]);
dp[i][2] = max(dp[i-1][1] + A[i][2], dp[i-1][2]);

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n; cin>>n;
        int dp[n+1][3] = {0};
        int A[n+1][3] = {0};
        for(int i = 1; i <= n; i++) cin>>A[i][1];
        for(int i = 1; i <= n; i++) cin>>A[i][2];
        for(int i = 1; i <= n; i++){
            dp[i][1] = max(dp[i-1][2] + A[i][1], dp[i-1][1]);
            dp[i][2] = max(dp[i-1][1] + A[i][2], dp[i-1][2]);
        } 
        cout<<max(dp[n][1],dp[n][2]) <<'\n';
    }
   
    return 0;
}
/************************
이건 어떻게 한 거지??
for (int j = 1; j < n; ++j) {
			if (j == 1) {
				d[0][j] += d[1][j-1];
				d[1][j] += d[0][j-1];
			}
			else {
				d[0][j] += max(d[1][j-1], d[1][j-2]);
				d[1][j] += max(d[0][j-1], d[0][j-2]);
			}
		}


****************************/

2. https://www.acmicpc.net/problem/2293

2293번: 동전 1

문제 : n 가지의 동전을 적당히 사용해서 가치의 합을 k원이 되도록 하는 경우의 수를 구하시오.

1 <= n <= 100, 1 <= k <= 10000

dp[i] : i원을 만들 수 있는 경우의 수

맨 처음 동전으로 만들 수 있는 모든 금액을 1씩 증가시킵니다.(0원도 포함)

그 다음은 나머지 동전에 대해 현재 금액의 경우의 수를 각 동전을 더해 만들 수 있는 금액에 더해주는 과정을 해줍니다.

#include <iostream>

using namespace std;
int n,k;
int A[110];
int dp[10010]; 
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i = 1; i <= n ; i++) {cin>>A[i];}
    for(int i = 0; i <= k; i += A[1]) dp[i] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 0; j + A[i] <= k; j++) dp[j + A[i]] += dp[j];
    }
    cout<<dp[k];
    return 0;
}

3. 동전2 https://www.acmicpc.net/problem/2294

2294번: 동전 2

#include <iostream>
#include <cstring>
using namespace std;
int n,k;
int A[110];
int dp[10010]; 
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i = 0 ; i < n; i++) cin>>A[i];
    dp[0] = 1;
    for(int i = 0; i <= k; i++){
        dp[i] = 100010;
        for(int j = 0; j < n; j++){
           if(i == A[j]) {dp[i] = 1;break;}
           if(i > A[j]) dp[i] = min(dp[i - A[j]] + 1, dp[i]);
        }   
    }
    if(dp[k] > 100000) cout<<-1;
    else cout<<dp[k];
    return 0;
}