[백준] 알고리즘 3-7일차 다이나믹 프로그래밍
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
포도주를 마셔도되고, 안마셔도 상관없다. 다만 연속으로 3번은 마실 수 없다. 연속한지 안한지를 검토하기 위해 2차원 배열로 해결할 수 있다.
dp[i][j] i번째포도주를 j(몇번 연속으로 마셨는가?)를 기록하는게 필요하다.
i번째 포도주를 안마셨을 때를 0이라 해보자.
그렇다면 포도주를 i-1번째는 마셔도되고 안마셔도되고 2번연속이여도 상관이없다.
dp[i][0] = max({ dp[i - 1][0],dp[i - 1][1],dp[i - 1][2] });
i번째 포도주를 1번연속 마셨다는 의미는 무엇일까
i-1번째 포도주에는 i번째의 1번연속을 만족시켜줘야 하니 i-1번째는 마시면 안된다라고 생각하면 된다.
dp[i][1] = dp[i - 1][0] + arr[i];
2번연속도 마찬가지이다.
dp[i][2] = dp[i - 1][1] + arr[i];
#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001][3]; // n번째 포도주를 0,1,2번 연속해서 마시는 경우의 수
int arr[10001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) {
dp[i][0] = max({ dp[i - 1][0],dp[i - 1][1],dp[i - 1][2] });
dp[i][1] = dp[i - 1][0] + arr[i];
dp[i][2] = dp[i - 1][1] + arr[i];
}
int ans = 0;
ans = max({ dp[n][0],dp[n][1],dp[n][2] });
cout << ans;
}1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
우선 삼각형을 복잡하게 보지말고, 이런식으로 있다고 생각하여 문제를 풀자.
이전의 다이나믹은 마지막 숫자를 정하여 조건에따라 이전 값들을 결정해주었다.
이번문제는 a는 b,c를 고를 수 있다. 반대로 생각해면 b가 왔을 때 어디에서 올 수 있는지를 살펴보면된다.
i,j라고 봤을때 반대로 우리는 올라가야하닌깐 빨간색에 표시해둔데로 좌표를 설정한다면 거슬러 올라가게 되는 것이다.
#include <iostream>
#include <algorithm>
using namespace std;
int arr[501][501];
int dp[501][501];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> arr[i][j];
}
}
dp[1][1] = arr[1][1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dp[n][i]);
cout << ans;
}11055번: 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수
www.acmicpc.net
가장 긴 증가하는 부분 수열과 똑같은데, 다른점은 d[i]에 증가하는 합의 최댓값을 저장하는 것이다.
결국엔 가장 긴 증가하는 길이를 구할때는 자기자신인 +1의 길이값을 해줬지만 여기서는 arr[i]값을 더해주면된다.
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001];
int dp[1001]; //n번째까지의 증가 부분 수열 중에서 합이 가장 큰
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
dp[i] = arr[i];
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = max(dp[j] + arr[i], dp[i]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(dp[i], ans);
}
cout << ans;
}11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
-> arr[i]를 뒤집어서 가장 긴 증가하는 부분수열을 구하는 방법
-> 가장 긴 증가하는 부분 수열에서 감소하는 것으로만 바꿔줘서 해결하는 방법
arr[i]<arr[j] 일때 dp[i] 값들을 비교해서 최대 길이를 저장시켜준다. 소스코드를 참고하자
-> dp[i] = i번째에서 시작하는 가장 긴 감소하는 부분 수열의 길이
i의 값을 n부터 시작해서 뒤에서부터 문제를 해결할 수 있다. 이 부분은 그다음 문제에서 적용할 것이다.
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001];
int dp[1001]; //n번째까지의 감소 하는 부분 수열의 길이의 최대값
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (arr[i] < arr[j]) {
dp[i] = max(dp[j] + 1, dp[i]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
cout << ans;
}11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
dp[i]=i번째까지 증가하는 부분 수열의 최장 길이
dp1[i] = i번째부터 시작하는 감소하는 부분 수열의 최장 길이
결국엔 i번째의 중복이 2번있으니 마지막에 하나를 빼준다.
이전까지는 다이나믹을 해결할 때 이전의 값을 이용해서 현재의 값을 도출해내는 방식을 이용했지만, i번째부터 시작하는 경우는 이전의 값으로 도출해낼 수 없으니 i번째 이후의 값들을 이용해서 도출해내야 한다. 즉 반복문을 반대로 시작하면 차근차근 구해나갈 수 있다.
#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;
int arr[1001];
int dp[1001];
int dp1[1001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = max(dp[j] + 1, dp[i]);
}
}
}
for (int i = n; i >= 1; i--) {
dp1[i] = 1;
for (int j = i + 1; j <= n; j++) {
if (arr[i] > arr[j]) {
dp1[i] = max(dp1[j] + 1, dp1[i]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dp[i] + dp1[i] - 1);
cout << ans;
}13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
이전의 연속합문제에서는 dp[i] = i번째로 끝나는 연속하는 가장 큰 합이다.
이 문제에서는 연속하는건 같지만 i번째를 제거할 수도있는 문제이다.
경우의 수는 2가지이다.
1) i를 제거한다.
2) i를 제거하지 않는다.
제거를 하지 않더라도 최대가 될 수 있고, 제거를 해야만 최대가 될 수도 있기 때문이다.
우리는 제거하지 않은 연속합을 dp에 저장을 먼저하자.
그다음 i번째를 제거하였을 경우 어떻게 최대값을 저장시킬 수 있는지 생각해야한다.
그림에서와 같이 i번째를 제거한다면 i-1번째와 i+1번째가 연속할 수 있다.
앞의 문제에서 i번째로 시작하는 부분 수열에대해서 학습하였다.
여기에서도 우리가 i-1, i+1부분을 연결시켜 최대합을 저장시키기 위해서는 i번째를 시작으로 하는 최대합을 저장시켜줄 필요가 있다. 이것을 dp1이라 설정하고 저장을 하자.
그렇다면 우리는 정답을 도출해낼때 제거하지 않았을 경우의 최대를 먼저구한다음 i번째를 제거하여 i-1과 i+1을 더해서 최대 정답을 도출해낼 수 있다.
10
10 -4 3 1 5 6 -35 12 21 -1
간단하게 예시를 들어보자
i=2일때 -4를 삭제한다고 생각해보자
그렇다면 10 3 ~~ 으로 배열이 생길 것이다.
우리는 i번째를 마지막으로 하는 최대합을 구했고, i번째로 시작하는 최대합을 이미 구한상태이다.
그렇다면 i-1번째와 i+1번째를 더해준다면, 연속하는 i번째를 제거한 최대합과 비교할 수 있을 것이다.
#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;
int arr[100001];
int dp[100001];
int dp1[100001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) { // i번째까지 연속하는 최대합
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
}
dp1[n] = arr[n];
for (int i = n-1; i >= 1; i--) { // i 번째부터 시작하는 연속하는 최대합
dp1[i] = max(dp1[i + 1] + arr[i], arr[i]);
}
int ans = dp[1];
for (int i = 2; i <= n; i++) ans = max(ans, dp[i]); // 제거하지 않았을 때의 최대합
for (int i = 2; i <= n - 1; i++) {
ans = max(ans, dp[i - 1] + dp1[i + 1]);
}
cout << ans;
}