Dynamic Programming I
#11048 이동하기
입력
첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.
출력
첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.
풀이
답
#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)이 주어진다. 둘째 줄에는 (0 ≤ ≤ 100)가 주어진다.
출력
재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -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을 출력한다.
풀이
가 팰린드롬이면 도 팰린드롬
이를 이용해서 길이가 짧은 것부터 찾자.
답
#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을 구성하자.
답
#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][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의 길이를 출력한다.
풀이
답
#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인 경우에는 둘째 줄을 출력하지 않는다.
풀이
가 과 다른 경우에만 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;
}
Author And Source
이 문제에 관하여(Dynamic Programming I), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dnr6054/Dynamic-Programming-I저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)