[백준/C++] 2156 포도주 시식 (S1)
| 유형 | 난이도 | 완료일 | 링크 | 특이사항 |
| DP | 실버1 | 23/02/25 | https://www.acmicpc.net/problem/2156 |
내 코드
#include <iostream>
#include <algorithm>
using namespace std;
int arr[10000];
int sum[3][10000];
int main(void)
{
int n;
cin >> n;
for(int i = 0; i< n; i++)
{
cin >> arr[i];
}
sum[0][0] = arr[0]; //이어짐
sum[1][0] = arr[0]; //한 칸 뜀
sum[2][0] = arr[0]; // 두 칸 뜀
if(n > 1)
{
sum[0][1] = arr[0] +arr[1];
sum[1][1] = arr[1];
sum[2][1] = arr[1];
}
if(n > 2)
{
sum[0][2] = arr[1]+arr[2];
sum[1][2] = arr[0]+arr[2];
sum[2][2] = arr[0]+arr[2];
}
if(n > 3)
{
sum[0][3] = sum[1][2] + arr[3];
sum[1][3] = sum[0][1] + arr[3];
sum[2][3] = sum[0][1] + arr[3];
}
if(n > 4)
{
sum[0][4] = arr[0] + arr[1] + arr[3] + arr[4];
sum[1][4] = max(sum[0][2], sum[1][2]) + arr[4];
sum[2][4] = arr[0] + arr[1] + arr[4];
}
for(int i = 5; i<n; i++)
{
sum[0][i] = arr[i] + max(sum[1][i-1], sum[2][i-1]);
sum[1][i] = arr[i] + max(max(sum[1][i-2],sum[2][i-2]), sum[0][i-2]);
sum[2][i] = arr[i] + max(max(sum[1][i-3],sum[2][i-3]), sum[0][i-3]);
}
int max = 0;
int temp = 0;
temp = sum[0][n-1];
if(temp > max)
max = temp;
temp = sum[1][n-1];
if(temp > max)
max = temp;
temp = sum[2][n-1];
if(temp > max)
max = temp;
temp = sum[0][n-2];
if(temp > max)
max = temp;
temp = sum[1][n-2];
if(temp > max)
max = temp;
temp = sum[2][n-2];
if(temp > max)
max = temp;
cout << max;
}2579 계단 오르기와 비슷한 문제였다. 계단 오르기는 진행 방향이 주어지고 2칸 이상 뛰어넘을 수 없다는 제약이 존재하지만 이 문제에서는 그런 제약이 없다. 그래서 처음엔 2칸을 건너뛰어야 하는 경우가 있다는 것을 생각하지 못하고 풀어서 계속 틀렸었다.
예를 들어 100 100 1 1 100 100 → 이렇게 수가 주어지면, 양 옆의 100을 취하기 위해서 가운데 1 1 을 포기해야 한다. 따라서 n번째 포도주 잔을 선택하는 경우의 수는 세 가지로 나뉜다. 첫 째는 n-1과 연속하는 것(이 경우 n-1은 n-2과 떨어져 있어야 한다), 둘 째는 n-1을 건너뛰고 n-2가 선택된 것, 셋 째로 n-3이 선택 되고 n-1과 n-2 모두 선택되지 않은 것이다. 각 경우에 따른 최댓값을 누적해가며 저장해두면 마지막 n-1번째와 n번째 포도잔 선택시의 누적 합 중에서 가장 큰 값이 정답이 된다. n-1 또는 n은 무조건 선택될 수 밖에 없기 때문이다.(n-1,n-2 모두 선택 안하는 경우가 최댓값일 수 없다. 놓치는 것 없이 추가만 되기 때문에)
n=1~4인 경우들 까지는 for문의 규칙과 다르게 값이 정해지므로 하나씩 직접 할당해주었고 n=5이상부터는 for문으로 값을 할당하였다. 세 가지 경우마다 선택될 수 있는 후보가 여럿 있어서 for문을 짜는게 꽤 헷갈렸다.
더 간결한 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n; cin >> n;
int a[10001]={0};
int dp[10001]={0};
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
dp[0] = 0;
dp[1] = a[1];
dp[2] = a[1] + a[2];
for(int i=3; i<=n; i++){
dp[i] = max({dp[i-3]+a[i-1]+a[i], dp[i-2]+a[i], dp[i-1]});
}
printf("%d\\n", dp[n]);
}
dp[i] = max({dp[i-3]+a[i-1]+a[i], dp[i-2]+a[i], dp[i-1]});
이 점화식으로 내 코드처럼 310000의 배열이 아니라 110000의 배열만으로 문제를 해결할 수 있었다.
다른 풀이를 보니 나도 방법이 있을 것 같았는데 더 생각해보지 않고 그냥 무식하게 구현한 것이 아쉽다.
핵심은, 난 n번째 칸을 생각할 때 n번째 칸을 무조건 선택한 경우로 생각했는데, 꼭 n번째의 포도주를 선택할 필요 없이 그냥 ‘n번째 까지의 최대 합’을 저장한다는 생각의 차이인 것 같다. 결국 n번째 까지의 합의 경우의 수는 마찬가지로 세 가지이고 그 중 가장 큰 값을 누적해가며 저장하는 것을 반복하면 된다.