문제 정보
백준 ( BOJ ) 2156번 포도주 시식
문제 풀이 : 다이나믹 프로그래밍 ( DP )
문제 출처 : https://www.acmicpc.net/problem/2156
문제 풀이
이 문제는 다이나믹 프로그래밍 문제입니다.
같은 dp 여도 2가지 방법이 있는데요
하나는 1차원 dp, 하나는 2차원 dp가 있습니다.
저는 여기서 2차원 dp를 사용하였습니다.
(정확히는 배열 3개)
우선 규칙을 찾아보자면,
각 포도주잔은 3가지 경우의 수가 있습니다.
안마시는것, 처음마시는것, 두번째 마시는것
A번째를 안마실때의 값은 뭐일까요?
A-1번째를 처음마시는것, 두번째 마시는것, 안마시는것 중 제일 큰 값이 A번째 안마셨을때 가장 큰 값입니다.
두번 연속 안마시는것도 ! 꼭 까먹지 말고 포함 해야만 해요
예를들어, 9 9 1 1 9 9 이런식이면, 4번쨰 1에서 9+9 가 아닌 다른 값을 찾게 될 테니까요.
그럼 A번쨰를 처음마시는 것은?
당연히 A-1을 안마시고 A를 먹는거니 A-1안마시는것 + A번째 포도주양
마지막으로 A번째를 두번째 마시는 것은
A-1번째를 처음으로 마시는것 + A번째 포도주양 이 됩니다.
for (int i = 1; i < n; i++) {
cin >> temp;
skip[i] = bigest(skip[i - 1], first[i - 1], second[i - 1]);
first[i] = skip[i - 1] + temp;
second[i] = first[i - 1] + temp;
}
이렇게 짜시면 되요.
2차원 dp라면 dp[i][0], dp[i][1], dp[i][2] 가 각각 skip,first,second 가 되겠지만
저는 보기 쉽게 각각 배열로 만들었습니다.
코드
#include <iostream>
#include <vector>
using namespace std;
int bigest(int a, int b, int c) {
if (a >= b && a >= c)
return a;
if (b >= a && b >= c)
return b;
if (c >= a && c >= b)
return c;
}
int main() {
int n;
int temp;
cin >> n;
vector<int> skip(n, 0);
vector<int> first(n, 0);
vector<int> second(n, 0);
cin >> temp;
first[0] = temp;
for (int i = 1; i < n; i++) {
cin >> temp;
skip[i] = bigest(skip[i - 1], first[i - 1], second[i - 1]);
first[i] = skip[i - 1] + temp;
second[i] = first[i - 1] + temp;
}
cout << bigest(skip[n - 1], first[n - 1], second[n - 1]);
return 0;
}