Dynamic Programming I

Bard·2021년 1월 24일

Algorithm

목록 보기

3/5

#11048 이동하기

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

풀이

$d(i,j) = max(\{d(i-1, j), d(i, j-1), d(i-1, j-1)\})$

답

#include<bits/stdc++.h>

using namespace std;

int m[1001][1001];
int d[1001][1001];
int main(){
    int N,M;
    cin>>N>>M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin>>m[i][j];
    d[0][0]=m[0][0];
    for(int i=1;i<N;i++)
        d[i][0] = m[i][0]+d[i-1][0];
    for(int j=1;j<M;j++)
        d[0][j] = m[0][j]+d[0][j-1];
    for(int i=1;i<N;i++)
        for(int j=1;j<M;j++)
            d[i][j] = m[i][j]+ max({d[i-1][j], d[i][j-1], d[i-1][j-1]});
    cout<<d[N-1][M-1];

}

#11060 점프 점프

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 $A_i$ (0 ≤ $A_i$ ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이

$for\;i\;=\;1\;to\;N:$
$\qquad for\;j\;=\;1\;to\;A_i:$
$\qquad\qquad d(i+j)=min(d(i+j), d(i)+1)$

답

#include<bits/stdc++.h>

using namespace std;

int d[1200];
int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
        d[i]=1e9;
    d[0]=0;
    for(int i=0;i<N;i++){
        int t;
        cin>>t;
        for(int j=1;j<=t;j++)
            d[i+j]=min(d[i+j], d[i]+1);
    }
    cout<<((d[N-1]!=1e9)?d[N-1]:-1);
}

#10942 팰린드롬?

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

풀이

$S$ 가 팰린드롬이면 $aSa$ 도 팰린드롬
이를 이용해서 길이가 짧은 것부터 찾자.

$for\;l=2\;to\;N-1:$
$\qquad for\;i=1\;to\;N:$
$\qquad\qquad$ $d(i, i+l)=((A_i==A_i+l)\;and\;d(i+1, i+l-1))$

답

#include<bits/stdc++.h>

using namespace std;

bool d[4001][4001];
int a[4001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>a[i+1];
    for(int i=1;i<=N;i++){
        d[i][i]=true;
        if (a[i]==a[i - 1]){
            d[i-1][i]=true;
        }
    }
    for(int l=2;l<=N-1;l++)
        for(int i=1;i<=N;i++)
            d[i][i+l]=(a[i]==a[i+l] && d[i+1][i+l-1]);

    int M;
    cin>>M;
    for(int i=0;i<M;i++){
        int s,e;
        cin>>s>>e;
        cout<<d[s][e]<<"\n";
    }
}

#15989 1, 2, 3 더하기 4

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

항상 오름차순 수열만 생각.
1로 끝나는 수열, 2로 끝나는 수열, 3으로 끝나는 수열로 나누어서 dp table을 구성하자.

$d[i][1]=1$
$d[i][2]=d[i-2][1]+d[i-2][2]$
$d[i][3]=d[i-3][1]+d[i-3][2]+d[i-3][3]$

답

#include<bits/stdc++.h>

using namespace std;

int d[10001][4];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;

    d[1][1]=1;
    d[2][1]=1;
    d[2][2]=1;
    d[3][1]=1;
    d[3][2]=1;
    d[3][3]=1;

    for(int i=4;i<=10000;i++){
        d[i][1]=1;
        d[i][2]=d[i-2][1]+d[i-2][2];
        d[i][3]=d[i-3][1]+d[i-3][2]+d[i-3][3];
    }

    while(T--){
        int q;
        cin>>q;
        cout<<d[q][1]+d[q][2]+d[q][3]<<'\n';
    }
}

#11066 파일 합치기

#13974 파일 합치기 2

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 5000)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

풀이

전형적인 Knuth Optimization 문제

$dp[i][j] = min(dp[i][k] + dp[k+1][j]) + s[j] - s[i-1]$

꼴이 다음 네 조건을 모두 만족한다.

점화식 꼴 : DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j] (i < j < k)
사각 부등식(Quadrangle inequality) : C[a][c] + C[b][d] ≤ C[a][d] + C[b][c] (a ≤ b ≤ c ≤ d)
단조성(monotonicity) : C[b][c] ≤ C[a][d] (a ≤ b ≤ c ≤ d)
단, c(비용)은 k에 독립적

따라서 dp[i][j]가 최소가 되기 위한 k를 p[i][j]라고 할 때, p[i][j-1] ≤ p[i][j] ≤ p[i+1][j]를 만족한다.

답

#include<bits/stdc++.h>

using namespace std;

int T, N, dp[5001][5001], p[5001], psum[5001], num[5001][5001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    for(cin>>T;T--;){
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>p[i];
            psum[i]=psum[i-1]+p[i];
        }
        for(int i=1;i<=N;i++)
            num[i-1][i]=i;
        for(int d=2;d<=N;d++){
            for(int i=0;i+d<=N;i++){
                int j = i+d;
                dp[i][j]=1e9;
                for(int k=num[i][j-1]; k<=num[i+1][j]; k++){
                    int v = dp[i][k]+dp[k][j]+psum[j]-psum[i];
                    if(dp[i][j]>v){
                        dp[i][j]=v;
                        num[i][j]=k;
                    }
                }
            }
        }
        cout<<dp[0][N]<<'\n';
    }
}

#9251 LCS

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

풀이

$dp[i][j] = max({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + (s1[i] == s2[j])})$

답

#include <bits/stdc++.h>

using namespace std;

int dp[1005][1005], i, j;
char s1[1005], s2[1005];
int main()
{
    cin >> s1 + 1 >> s2 + 1;
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = max({dp[i][j - 1],
                            dp[i - 1][j],
                            dp[i - 1][j - 1] + (s1[i] == s2[j])});
    cout << dp[i - 1][j - 1];
    return 0;
}

#9252 LCS 2

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

풀이

$dp[i][j]$ 가 $dp[i-1][j-1]$ 과 다른 경우에만 LCS에 포함된다.

답

#include <bits/stdc++.h>

using namespace std;

int dp[1005][1005], i, j;
char s1[1005], s2[1005];
vector<char> v;
int main()
{
    cin >> s1 + 1 >> s2 + 1;
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = max({dp[i][j - 1],
                            dp[i - 1][j],
                            dp[i - 1][j - 1] + (s1[i] == s2[j])});
    cout << dp[--i][--j] << endl;
    while (i >= 1 && j >= 1){
        if (dp[i][j] == dp[i - 1][j])
            i--;
        else if (dp[i][j] == dp[i][j - 1])
            j--;
        else{
            v.push_back(s1[i]);
            i--, j--;
        }
    }
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i];
    return 0;
}

Bard

The Wandering Caretaker

이전 포스트

Möbius inversion formula (BOJ 1792)

다음 포스트