DP(3) - 부분 수열, 퇴사, 쉬운 계단 수
부분 수열 문제들 중 DP로 풀 수 있는 것들을 풀어보았다.
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int d[1003],a[1003];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
fill(d,d+n+1,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(a[j]<a[i]) d[i]=max(d[i],d[j]+1);
}
}
cout<<*max_element(d,d+n+1);
return 0;
}https://www.acmicpc.net/problem/11055
11055번: 가장 큰 증가하는 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는
www.acmicpc.net
이 문제는 스스로 풀어보았다. 처음에는 이런 식으로 투박하게 코드를 작성했는데
#include <bits/stdc++.h>
using namespace std;
int a[1003],d[1003];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
d[1]=a[1];
for(int i=1;i<=n;i++){
int mx=0;
for(int j=i;j>=1;j--){
if(a[i]>a[j]){
mx=max(mx,d[j]);
}
}
d[i]=a[i]+mx;
}
//for(int i=1;i<=n;i++) cout<<d[i]<<' ';
cout<<*max_element(d,d+n+1);
return 0;
}이렇게 하면 코드를 더욱 간략화 할 수 있었다.
#include <bits/stdc++.h>
using namespace std;
int a[1003],d[1003];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];d[i]=a[i];}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(a[i]>a[j]) d[i]=max(d[i],d[j]+a[i]);
}
}
cout<<*max_element(d,d+n+1);
return 0;
}https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
퇴사 2도 있는데 범위만 달라졌다. 코드는 퇴사 2 코드이다.
#include <bits/stdc++.h>
using namespace std;
int n,d[1500003],t[1500003],p[1500003];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>t[i]>>p[i];
for(int i=n;i>=1;i--){
//상담이 가능하면 (상담하는 경우나 안하는 경우 중 최댓값)을 고름
if(i+t[i]<=n+1) d[i]=max(d[i+t[i]]+p[i],d[i+1]);
//상담이 불가능하면
else d[i]=d[i+1];
}
cout << *max_element(d, d + n + 1);
return 0;
}https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
처음에는 이런 코드로 제출했는데 바로 틀렸습니다를 맞이했다. 너무 일차원적인 DP 문제만 풀어서 다른 풀이를 생각하지 못했는데 풀이를 보면서 이렇게도 할 수 있다는 것을 배웠다.
#include <bits/stdc++.h>
using namespace std;
long long n,d[1500003];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n; d[1]=9;
for(int i=2;i<=n;i++) d[i]=(d[i-1]%1000000000)*2 - 1;
cout<<d[n];
return 0;
}
#include <bits/stdc++.h>
using namespace std;
long long n,d[103][10];
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=1;i<=9;i++) d[1][i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=9;j++){
if(j==0) d[i][0]=d[i-1][1];
else if(j==9) d[i][9]=d[i-1][8];
else d[i][j]=d[i-1][j-1]+d[i-1][j+1];
d[i][j]%=1000000000;
}
}
long long sum=0;
for(int i=0;i<=9;i++) sum+=d[n][i];
cout<<sum%1000000000;
return 0;
}DP를 풀다보면 어려운 수학문제를 풀어내는 느낌이 든다. 그런 점이 재밌게 느껴진다.