Dynamic Programming II

#12865 평범한 배낭

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

풀이

$d(i,j) = max(d(i-1, j), d(i-1, j-w)+v)$

답

#include <iostream>

using namespace std;

int dp[105][100005];

int main()
{
    int N,K;
    cin>>N>>K;
    for(int i=1;i<=N;i++){
        int w,v;
        cin>>w>>v;
        for(int j=1;j<=K;j++){
            if(j<w) dp[i][j]=dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v);
        }
    }
    cout<<dp[N][K];
}

---

#1495 기타리스트

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

풀이

$if\;dp(i-1,j) :$
$\qquad if(j+V<=M) \;\;dp(i,j+V)=true;$
$\qquad if(j-V>=0) \;\;\;\;dp(i,j-V)=true;$

답

#include <iostream>

using namespace std;

bool dp[105][1005];

int main()
{
    int N,M,S,V;
    cin>>N>>S>>M;
    dp[0][S]=true;
    for(int i=1;i<=N;i++){
        cin>>V;
        for(int j=0;j<=M;j++){
            if(dp[i-1][j]){
                if(j+V<=M) dp[i][j+V]=true;
                if(j-V>=0) dp[i][j-V]=true;
            }
        }
    }
    for(int i=M;i>=0;i--){
        if(dp[N][i]){
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

---

#12869 뮤탈리스크

입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

풀이

dfs로 간단하게 해결할 수 있다. 메모이제이션을 이용한다.

답

#include <bits/stdc++.h>

using namespace std;

int dmg[6][3]={{9,3,1},{9,1,3},{3,9,1},{3,1,9},{1,9,3},{1,3,9}};
int dp[61][61][61];
int scv[3];

int dfs(int a, int b, int c){
    a=max(a,0);b=max(b,0);c=max(c,0);
    if(dp[a][b][c]!=-1) return dp[a][b][c];
    int ret = 1e9;
    for(int i=0;i<6;i++){
        ret=min(ret, dfs(a-dmg[i][0],b-dmg[i][1],c-dmg[i][2])+1);
    }
    dp[a][b][c]=ret;
    return ret;
}

int main()
{
    int N;
    cin>>N;
    memset(dp, -1, sizeof(dp));
    dp[0][0][0]=0;
    for(int i=0;i<N;i++){
        cin>>scv[i];
    }
    cout<<dfs(scv[0],scv[1],scv[2]);
}

---

#10422 괄호

입력

첫 번째 줄에 테스트케이스의 개수를 나타내는 T (1 ≤ T ≤ 100)가 주어진다. 두 번째 줄부터 각 테스트케이스마다 괄호 문자열의 길이를 나타내는 L이 주어진다. (1 ≤ L ≤ 5000)

출력

각 테스트 케이스에 대해 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하시오.

풀이

Catalan Number

$C_{n+1} = \sum_{k=0}^nC_kC_{n-k}$

답

#include <iostream>
#define P 1000000007
using namespace std;
long long C[5001];
int main(){
    C[0]=C[1]=1;
    for(int i=2;i<=5000;i++){
        for(int j=0;j<i;j++){
            C[i]+=C[j]*C[i-1-j];
            C[i]%=P;
        }
    }
    int N,t;
    for(cin>>N;N--;){
        cin>>t;
        if(t%2) cout<<"0\n";
        else cout<<C[t/2]<<'\n';
    }
}

---

#2293 동전 1

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 $2^{31}$보다 작다.

풀이

$d(j) = d(j)+d(j-v[i])$

답

#include<iostream>
using namespace std;

int v[101];
int dp[10001];

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>v[i];
    for(int i=0;i<=k;i++){
        if(i%v[0]==0)    dp[i]=1;
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<=k;j++){
            if(j>=v[i])    dp[j]=dp[j]+dp[j-v[i]];
        }
    }
    cout<<dp[k];
}

---

#2294 동전 2

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이

$d(j) = min(d(j),d(j-v[i])+1)$

답

#include<bits/stdc++.h>

int v[101];
int dp[10001];

using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=k;i++) dp[i]=1e9;
    for(int i=0;i<n;i++)
        cin>>v[i];
    dp[0]=0;
    for(int i=0;i<n;i++)
        for(int j=v[i];j<=k;j++)
            dp[j]=min(dp[j],dp[j-v[i]]+1);
    cout<<((dp[k]!=1e9)?dp[k]:-1);
}

---

#11058 크리보드

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

풀이

$d(i) = min\{d(i),d(i-1)+1,d(i-(j+2))*(j+1)\}$

답

#include<bits/stdc++.h>

long long dp[101];

using namespace std;
int main(){
    int N;
    cin>>N;
    for(int i=1;i<=6;i++) dp[i]=i;
     for(int i=7;i<=100;i++) {
        for(int j=1;j<=i-3;j++){
            dp[i] = max({dp[i],dp[i-1]+1,(dp[i-(j+2)]*(j+1))});
        }
    }
    cout<<dp[N];
}

---