Dynamic Programming I

93991 단어 algorithmalgorithm

#11048 이동하기

입력

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

출력

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

풀이

d(i,j)=max({d(i1,j),d(i,j1),d(i1,j1)})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)이 주어진다. 둘째 줄에는 AiA_i

출력

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

풀이

for  i  =  1  to  N:for\;i\;=\;1\;to\;N:

#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을 출력한다.

풀이

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

for  l=2  to  N1:for\;l=2\;to\;N-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]=1d[i][1]=1

#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[i1]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][j1],dp[i1][j],dp[i1][j1]+(s1[i]==s2[j]))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][j]dp[i1][j1]dp[i-1][j-1]

#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;
}

좋은 웹페이지 즐겨찾기