DP(1) - 연습문제 풀기
https://www.youtube.com/watch?v=5leTtB3PQu0&t=15s
어쩌다 보니 이제 DP를 배울 때가 왔다. 지금까지 해왔던 것들 중 DP가 가장 어렵게 느껴졌다... 이것도 많이 해보면 BFS처럼 늘 것이라 믿는다.
https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int d[1000003];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
d[1]=0;
for(int i=2;i<=n;i++){
//기본 상태
d[i]=d[i-1]+1;
//나누어 떨어질 경우
if(i%2==0) d[i]=min(d[i],d[i/2]+1);
if(i%3==0) d[i]=min(d[i],d[i/3]+1);
}
cout<<d[n];
return 0;
}https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int d[13];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
d[1]=1; d[2]=2; d[3]=4;
for(int i=4;i<11;i++){
d[i]=d[i-1]+d[i-2]+d[i-3];
}
int k; cin>>k;
while(k--){
int n; cin>>n;
cout<<d[n]<<'\n';
}
return 0;
}이 문제의 점화식은 간단해서 쉽게 풀 수 있다.
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
이 문제가 너무 어렵게 느껴졌는데 한 번 그림으로 그려보니 이해할 수 있었다.
#include <bits/stdc++.h>
using namespace std;
int d[303][3]; //계단 연속으로밟은계단(3개면 안됨)
int s[303];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
d[1][1]=s[1]; d[1][2]=0; //불가능함
d[2][1]=s[2]; d[2][2]=s[1]+s[2];
for(int i=3;i<=n;i++){
d[i][1]=max(d[i-2][1],d[i-2][2])+s[i];
d[i][2]=d[i-1][1]+s[i];
}
cout<<max(d[n][1],d[n][2]);
return 0;
}
이 부분에서 한 번 벽을 느꼈었다.
영상에서는 1차원 배열로 이 문제를 푸는 법도 알려준다. 밟을 계단을 고르지 않고, 밟지 않을 계단을 고르는 것이다.
D[i] : i번째 계단까지 올라섰을 때 밟지 않을 계단의 합의 최솟값. (단 i번째 계단은 반드시 밟지 않을 계단임)
이때 i번째 계단을 밟지 않는다는 말은 i-1 번째 계단은 무조건 밟는다는 의미이다.
i-1번째 계단을 밟으려면 i-2, 혹은 i-3번째 계단을 밟아야 한다(=i-3번째 계단을 밟지 않거나, i-2번째 계단을 밟지 않는다.)
https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
이 문제는 혼자 풀어보았다. 풀만한 문제였다.
#include <bits/stdc++.h>
using namespace std;
int d[1003][3]; //집 색깔
pair<pair<int,int>,int> RGB[1003];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin>>N;
for(int i=1;i<=N;i++){
int R,G,B; cin>>R>>G>>B;
RGB[i]={{R,G},B};
}
d[1][0]=RGB[1].first.first;
d[1][1]=RGB[1].first.second;
d[1][2]=RGB[1].second;
for(int i=2;i<=N;i++){
d[i][0]=min(d[i-1][1],d[i-1][2])+RGB[i].first.first;
d[i][1]=min(d[i-1][0],d[i-1][2])+RGB[i].first.second;
d[i][2]=min(d[i-1][0],d[i-1][1])+RGB[i].second;
}
cout<<min(min(d[N][0],d[N][1]),d[N][2]);
return 0;
}https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
강의를 보면서 진짜 감탄했다. 이런 생각이 물흐르듯이 나와야 카이스트 가고... 과학고 가고...
결국 1,2,3 더하기와 다를 것 없는 문제였다.
#include <bits/stdc++.h>
using namespace std;
int d[1003];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
d[1]=1; d[2]=2;
for(int i=3;i<=n;i++){
d[i]=(d[i-1]+d[i-2])%10007;
}
cout<<d[n];
return 0;
}https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
이 문제 어디선가 푸는 법을 배운 것 같다. 머리속에 풀이가 있어서 그냥 풀었다.
이 기법을 Prefix-sum 이라고 한다고 한다.
#include <bits/stdc++.h>
using namespace std;
int d[100003],input[100003];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++){cin>>input[i]; d[i]=d[i-1]+input[i];}
while(m--){
int a,b; cin>>a>>b;
cout<<d[b]-d[a-1]<<'\n';
}
return 0;
}