다이나믹 프로그래밍[Dynamic Programming] 연습하기 좋은 문제 및 풀이
알고리즘 문제풀이에서 벡터의 사용은 매우 좋은것 같다.
알고리즘을 간략하고 이해하기 쉽게 표현할 수 있다.
예를들어 d배열에서 최댓값을 찾는 등을 한줄로 표현할 수 있다.
cout << *max_element(d.begin(), d.end());
개인적으로 문제를 풀며 도저히 못 풀겠다는 생각이 들때는 애초에 문제에 대한 접근부터 잘 못 했을 경우가 크다.
이 경우에는 다른 사람의 코드를 보며 이해하고 자신의 것으로 만드는 것도 좋은 것 같다.
1463 : 1로만들기 www.acmicpc.net/problem/1463
풀이 및 코드
문제를 해석할때 하기 쉬운 실수는
3가지 연산을 순서대로 즉, '3으로 나눌 수 있을때 3으로 나누고
2로 나눌수 있을때 2로 나누고 1을 빼면 되지 않을까?' 라고 생각 할 수 있는데
이렇게 하면 안된다.
10의 경우
10-5-4-2-1 보다
10-9-3-1이 최소연산을 사용한다
고로 이문제는 다이나믹을 이용하여 풀어야 한다.
다이나믹을 적용 할 경우
1. D[n] = D[n/3]+1
2. D[n] = D[n/2]+1
3. D[n] = D[n-1}+1
으로 문제를 생각 할 수 있다.
Top-Down과 Bottom-UP으로 풀 수 있다.
//Top-Down
#include <iostream>
#include <algorithm>
using namespace std;
int db[1000002];
int go(int n) {
if (n == 1) return 1;
if (db[n] > 0) return db[n];
int ret = go(n - 1) + 1;
int temp;
if (n % 3 == 0) {
temp = go(n / 3) + 1;
if (ret > temp) ret = temp;
}
if (n % 2 == 0) {
temp = go(n / 2) + 1;
if (ret > temp) ret = temp;
}
db[n] = ret;
return ret;
}
int main(void) {
int x;
int cnt=0;
cin >> x;
cout << go(x)-1;
return 0;
}
//시간복잡도 O(N)//Bottom-Up
#include <iostream>
#include <algorithm>
using namespace std;
int db[1000002];
int main(void) {
int x;
db[1] = 0;
cin >> x;
for (int i = 2; i <= x; ++i) {
db[i] = db[i-1] + 1;
if (i % 2 == 0)
db[i] = min(db[i], db[i / 2] + 1);
if (i % 3 == 0)
db[i] = min(db[i], db[i / 3] + 1);
}
cout << db[x];
return 0;
}
//시간복잡도 O(N)
11726 : 2xn 타일링 www.acmicpc.net/problem/11726
풀이 및 코드
접근 방식을 잘못 접근할 경우 오래 해맬 수 있는 문제
#include <iostream>
using namespace std;
int db[1001];
int main(void) {
int n;
cin >> n;
db[1] = 1;
db[2] = 2;
for (int i = 3; i <= 1000; ++i) {
db[i] = db[i - 1] + db[i - 2];
db[i] = db[i] % 10007;
}
cout << db[n];
}
11727 : 2xn 타일링2 www.acmicpc.net/problem/11727
풀이 및 코드
#include <iostream>
using namespace std;
int db[1001];
int main(void) {
int n;
cin >> n;
db[1] = 1;
db[2] = 3;
for (int i = 3; i <= 1000; ++i) {
db[i] = db[i - 1] + 2*db[i - 2];
db[i] = db[i] % 10007;
}
cout << db[n];
}
11052 : 카드구매하기 www.acmicpc.net/problem/11052
풀이 및 코드
#include <iostream>
#include <algorithm>
using namespace std;
int p[1001];
int db[1000];
int main(void) {
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
cin >> p[i];
db[i] = p[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
db[i] = max(db[i], p[j] + db[i-j]);
}
}
cout << db[n];
}
2193 : 이친수 www.acmicpc.net/problem/2193
풀이 및 코드
n번째 자리에 무엇이 올 건지 결정하면서 풀면된다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
long long d[100][2];
d[1][0] = 0;
d[1][1] = 1;
for (int i = 2; i <= 90; ++i) {
d[i][1] = d[i - 1][0];
d[i][0] = d[i - 1][0] + d[i - 1][1];
}
int x;
cin >> x;
cout << d[x][0] + d[x][1];
}
10844 : 쉬운 계단 수 www.acmicpc.net/problem/10844
풀이 및 코드
마지막 n번째 자리에 올 수 있는 수가 무엇인지, 그때 앞에 있는 수가 무엇인지 생각하면서 풀면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
long long d[101][10];
int main(void) {
for (int i = 1; i <= 100; ++i) {
for (int j = 0; j <= 9; ++j) {
if (i == 1) {
d[i][j] = 1;
if (j == 0) d[1][0] = 0;
continue;
}
if (j == 0) {
d[i][0] = d[i - 1][1];
continue;
}
if (j == 9) {
d[i][9] = d[i - 1][8];
continue;
}
d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % 1000000000;
}
}
int x;
cin >> x;
cout << (d[x][0] + d[x][1] + d[x][2] + d[x][3] + d[x][4] + d[x][5] + d[x][6] + d[x][7] + d[x][8] + d[x][9]) % 1000000000;
}
11057 : 오르막 수 www.acmicpc.net/problem/11057
풀이 및 코드
n-1번째 자리에 어떤 수가 올 수 있는지 생각하면서 풀면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
long long d[1001][10];
int main(void) {
for (int i = 0; i < 10; ++i) d[1][i] = 1;
for (int i = 2; i <= 1000; ++i) {
for (int j = 0; j <= 9; ++j) {
for (int k = 0; k <= j; ++k) {
d[i][j] += d[i - 1][k];
d[i][j] %= 10007;
}
}
}
int x;
int ans=0;
cin >> x;
for (int i = 0; i <= 9; ++i) ans += d[x][i];
cout << ans%10007;
}
9465 : 스티커 www.acmicpc.net/problem/9465
풀이 및 코드
n번째 열에 어떤 스티커의 상태가 올 수 있는지 보고, 그때 앞에 올 수 있는 상태가 무엇인지 생각하면서 풀면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
long long d[100001][3];
int arr[100001][2];
int main(void) {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> arr[i][0];
}
for (int i = 1; i <= n; ++i) {
cin >> arr[i][1];
}
d[1][0] = 0;
d[1][1] = arr[1][0];
d[1][2] = arr[1][1];
for (int i = 2; i <= n; ++i) {
d[i][0] = max(max(d[i - 1][0], d[i - 1][1]), d[i - 1][2]);
d[i][1] = max(d[i - 1][0] + arr[i][0], d[i - 1][2] + arr[i][0]);
d[i][2] = max(d[i - 1][0] + arr[i][1], d[i - 1][1] + arr[i][1]);
}
cout << max(max(d[n][0], d[n][1]), d[n][2]) << endl;
}
}
2156 : 포도주 시식 www.acmicpc.net/problem/2156
풀이 및 코드
n번째 포도주가 0번 연속일때, n-1번째가 어떤 상태인지, 1,2번 연속일때 앞의 상태가 어떤지(세자리 수가 연속하면 안되는 부분에 주목.)
n개의 수를 나열할때 n-1에서 0번 연속했는지, 1번연속했는지, 2번연속했는지.
(2차원과 1차원으로 생각해보기)
이차원 다이나믹 : M[n][0], M[n][1], M[n][2]으로 나눠서 푸는 문제.
일차원 다이나믹 : D[n], 0번 연속 : D[n-1], 1번연속 : D[n-2]+ A[n], 2번연속 : D[n-3]+A[n]+A[n-1]
//이차원 다이나믹
#include <iostream>
#include <algorithm>
using namespace std;
int arr[10001];
int arrM[10001][3];
int main(void) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
arrM[0][1] = arr[0];
arrM[1][2] = arr[0] + arr[1];
arrM[1][0] = arr[0];
arrM[1][1] = arr[1];
arrM[2][0] = arr[0] + arr[1];
arrM[2][1] = arr[0] + arr[2];
arrM[2][2] = arr[1] + arr[2];
for (int i = 3; i <= n; ++i) {
arrM[i][0] = max(max(arrM[i - 1][0], arrM[i - 1][1]), arrM[i - 1][2]);
arrM[i][1] = arrM[i - 1][0] + arr[i];
arrM[i][2] = arrM[i - 1][1] + arr[i];
}
cout << max(max(arrM[n][0], arrM[n][1]), arrM[n][2]);
return 0;
}//일차원 다이나믹
#include <iostream>
#include <algorithm>
using namespace std;
int arr[10001];
int arrM[10001];
int main(void) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
}
arrM[1] = arr[1];
arrM[2] = arr[1] + arr[2];
for (int i = 3; i <= n; ++i) {
arrM[i] = arrM[i - 1];
if (arrM[i] < arrM[i - 2] + arr[i]) arrM[i] = arrM[i - 2] + arr[i];
if (arrM[i] < arrM[i - 3] + arr[i - 1] + arr[i]) arrM[i] = arrM[i - 3] + arr[i - 1] + arr[i];
}
cout << arrM[n];
return 0;
}
11053 : 가장 긴 증가하는 부분 수열 www.acmicpc.net/problem/11053
풀이 및 코드
LTS, 부분수열 : 수열에서 일부 선택한 수열(순서가 바뀌면 안됨.)
D[i]는 A[0~i]중 가장 긴 증가하는 부분수열
top-down으로 생각하면 쉬운문제.
A[i] > A[0~i-1]중에서
D[i] = max(D[0~i-1])+1
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> A(n), D(n);
for (int i = 0; i < n; ++i){
cin >> A[i];
D[i] = 1;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (A[j] < A[i] && D[i] < D[j]+1) {
D[i] = D[j] +1;
}
}
}
cout << *max_element(D.begin(), D.end());
return 0;
}
시간복잡도 : N * O(N) = O(N^2)
11055 : 가장 큰 증가하는 부분 수열 www.acmicpc.net/problem/11055
풀이 및 코드
11053을 풀었다면 짧은시간에 풀 수 있는 문제.
길이를 구하는 것이 아닌 합을 더하는 것이므로 1을 A[i]로 바꿔주면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> A(n), D(n);
for (int i = 0; i < n; ++i) {
cin >> A[i];
D[i] = A[i];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (A[j] < A[i] && D[i] < D[j] + A[i]) {
D[i] = D[j] + A[i];
}
}
}
cout << *max_element(D.begin(), D.end());
return 0;
}
11722 : 가장 긴 감소하는 부분 수열 www.acmicpc.net/problem/11722
풀이 및 코드
방법 1: 수열 A를 뒤집는다.
방법 2: 부등호를 바꿔준다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> A(n), D(n);
for (int i = 0; i < n; ++i) {
cin >> A[i];
D[i] = 1;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (A[j] > A[i] && D[i] < D[j] + 1) {
D[i] = D[j] + 1;
}
}
}
cout << *max_element(D.begin(), D.end());
return 0;
}
11054 : 가장 긴 바이토닉 부분수열 www.acmicpc.net/problem/11054
풀이 및 코드
가장 긴 증가하는 부분 수열(D)과 가장 긴 감소하는 수열(D2)를 구한다음
D + D2 - 1을 하면된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> A(n),A2(n), D(n), D2(n), D3(n);
for (int i = 0; i < n; ++i) {
cin >> A[i];
D[i] = 1;
D2[i] = 1;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (A[j] < A[i] && D[i] < D[j] + 1) {
D[i] = D[j] + 1;
}
}
}
for (int i = 0; i < n; ++i) {
A2[i] = A[n - i-1];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (A2[j] < A2[i] && D2[i] < D2[j] + 1) {
D2[i] = D2[j] + 1;
}
}
}
for (int i = 0; i < n; ++i) {
D3[i] = D[i] + D2[n-i-1] - 1;
}
cout << *max_element(D3.begin(), D3.end());
return 0;
}
1912 : 연속합 www.acmicpc.net/problem/1912
풀이 및 코드
음수를 선택하지 않는 것이 최대일까? 라는 고민을 할 수 있지만 아래의 예시를 보면 이는 아니라는 것을 금방 알 수 있다.
ex) 10, -1, -1, 10 --> 18
1. A[i-1]로 끝나는 연속합이 포함되는 경우
2. 새로운 연속합을 시작하는 경우
위의 경우를 식으로 나타내면 된다.
점화식을 구한다.
D[i] = A[i]를 마지막으로 하는 연속합 중 가장 큰 값
D[i] = (D[i-1] + A[i]) or (A[i])
(D[i-1] + A[i]) or (A[i]) 중 더 큰 값을 넣자
답은 D[i]중 최대값을 고른다.
시간복잡도 O(N)
총 N개의 칸을 채우는데 비교해야 되는 것이 앞에 것과 더하는 것과 자기자신 밖에 없다.
최대값이 0보다 작은수가 있을 수 있으므로
ans=0;
if(ans<d[i]) ans=d[i];
와같은 식 사용 주의하자.
ans = d[i]; or ans = -2147483648;
이렇게 해서 최댓값을 구하는 것이 좀 더 좋은 방식이다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> v(n), d(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
d[0] = v[0];
for (int i = 1; i < n; ++i) {
if (d[i - 1] + v[i] <= v[i])
d[i] = v[i];
else
d[i] = d[i - 1] + v[i];
}
cout << *max_element(d.begin(), d.end());
}
2579 : 계단 오르기 www.acmicpc.net/problem/2579
풀이 및 코드
포두주 시식과 비슷한 문제
D[i][j] = i번째 계단에 올라갔을 때, 최대 점수. (i번째 계단은 j개 연속해서 올라온 계단임.)
D[i][0] = 0개연속, i번째 계단에 올라가야 하기 때문에 불가능한 경우
D[i][1] = 1개 연속, i-1번째 계단은 밟으면 안됨.
D[i][2] = 2개 연속, i번째 계단은 밟아야 하고, 반드시 1개 연속해서 올라온 계단이어야 함
이차원으로 풀었지만, 일차원으로도 풀 수 있는 문제
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> v(n), d(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
d[0] = v[0];
for (int i = 1; i < n; ++i) {
if (d[i - 1] + v[i] <= v[i])
d[i] = v[i];
else
d[i] = d[i - 1] + v[i];
}
cout << *max_element(d.begin(), d.end());
}
1699 : 제곱수의 합 www.acmicpc.net/problem/1699
풀이 및 코드
1,2,3더하기 문제와 매우 비슷하다.
올수 있는 수 : 1^2, 2^2, 3^2, ...... ,
D[i] = i를 제곱수의 합으로 나타냈을 때, 필요한 항의 최소 개수
D[i] = min(D[i-j^2]+1) (1<=i<=j^2)
#include <iostream>
using namespace std;
int main(void) {
int n;
cin >> n;
int d[100001];
d[0] = 0;
for (int i = 1; i <= n; ++i) {
d[i] = i;
for (int j = 1; j*j <= i; ++j) {
if (d[i] > d[i - j * j] + 1) d[i] = d[i - j * j] + 1;
}
}
cout << d[n];
}
시간복잡도 : O(N*√N) = N개의 칸을 채우는데 한칸당 걸리는 시간 루트N
2133 : 타일채우기 www.acmicpc.net/problem/2133
풀이 및 코드
점화식처럼 풀면 되는 문제
A[2]=3
A[4] = A[2]*3 + 2;
A[6] = A[4]*3 + A[2]*2 + 2
A[8] = A[6]*3 + A[4]*2 + A[2]*2 + 2
∵중간에 구간을 나눌 수 없는 N길이의 타일은 2개이기 때문, 홀수길이는 만들 수 없음.
9461 : 파도반 수열 www.acmicpc.net/problem/9461
풀이 및 코드
피보나치 수와 비슷한 문제
그림을 보면서 규칙을 찾는문제
D[i] = D[i-1] + D[i-5]; // 변의 길이를 더함으로
D[i] = D[i-2] + D[i-3]; // 정삼각형 및 평행선 규칙에 의해서
#include <iostream>
using namespace std;
long long d[101];
int main() {
int n, t;
d[1] = 1;
d[2] = 1;
d[3] = 1;
for (int i = 4; i <= 100; ++i) {
d[i] = d[i - 2] + d[i - 3];
}
cin >> t;
for (int i = 0; i < t; ++i) {
cin >> n;
cout << d[n]<<endl;
}
return 0;
}
2225 : 합분해 www.acmicpc.net/problem/2225
풀이 및 코드
D[K][N]= 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
?+?+ ... + ? + L = N
D[K][N]
?+?+ ... + ? = N-L
D[K-1][N-L]
D[K][N] += D[k-1][N-L] ( 0<= L <= N)
#include <iostream>
using namespace std;
long long d[201][201];
int main(void) {
int N, K;
cin >> N >> K;
d[0][0] = 1LL;
for (int i = 1; i <= K; ++i) {
for (int j = 0; j <= N; ++j) {
for (int k = 0; k <= j; ++k) {
d[i][j] += d[i - 1][j - k];
d[i][j] %= 1000000000;
}
}
}
cout << d[K][N];
}
2011 : 암호코드 www.acmicpc.net/problem/2011
'algorithm > basis' 카테고리의 다른 글
| 정렬(Sorting), Stable_Sorting (0) | 2021.01.31 |
|---|---|
| 수학 (0) | 2021.01.08 |
| 다이나믹 프로그래밍[Dynamic Programming] (0) | 2020.12.16 |
| 자료구조 : 문자열 (0) | 2019.06.06 |
| 자료구조 : 덱(deque) (0) | 2019.06.06 |
