문제 이해 단계
포도주 n개가 주어지고 순서대로 1부터 n까지의 번호가 붙여진다.
1번 포도주부터 순서대로 마시는데 연속해서 3잔을 마실수는 없다.
그리고 각 포도주에는 점수가 있고, 가장 많은 점수를 구하는 경우의 수를 구하는 문제
문제 접근 단계
이 문제에서 핵심 조건은 3잔을 연속해서 마실 수 없다는 조건이다.
그렇기 때문에 이 점을 중심으로 풀이를 생각했다.
이전에 계단 오르기란 문제를 풀었는데, 문제가 유사한 느낌이 들어서
이것도 DP로 접근해 보면 되지 않을까? 싶었다.
임의의 포도주 위치 N을 잡고 해당 포도주를 중심으로 식을 세워보기로 했다.
선택한 포도주를 N이라고 했을 때, 포도주 N-2와 N-1와의 관계를 살펴보자.
2개까지만 살펴보는 이유는, 3잔을 연속해서 마실 수 없기 때문에
그 이상은 무의미하기 때문이다.
포도주 N을 먹는다고 가정했을 때 나올 수 있는 경우의 수는
(먹는 것을 O, 먹지 않는 것을 X라고 가정)
1.???? XXO
2.???? XOO
3.???? OXO
앞에???? 는 3잔을 연속해서 마실 수 없다는 조건을 맞췄다는 가정을 했고,
최댓값을 구하는 경우의 수라고 생각한다.
이때 우리는 최댓값을 구하는 것이기 때문에
1번의 경우는 2번 3번보다 무조건 작을 수밖에 없다.
즉, 이 경우는 제외해 줘도 되는 케이스이다.
따라서 우리는 2번 3번 케이스 중 더 큰 값을
N번째 포도주를 선택했을 때의 얻을 수 있는 최댓값이라고 생각할 수 있다.
N번째까지 도달했을 때, 얻을 수 있는 최댓값을 DP [N]이라고 한다면
2번 케이스 -> DP [N] = DP [N-3]+(N-1 와인 점수) + (N 와인 점수)
3번 케이스 -> DP [N] = DP [N-2]+(N 와인 점수)
3번 케이스가 DP [N-2]로 다르게 나온 이유는
N-2번째를 무조건 먹기 때문에 항상 그 점수가 포함되기 때문이다.
그렇기 때문에 최댓값에 항상 도움을 주기 때문에
DP [N-3] + N-2 와인 점수 = DP [N-2]와 같기 때문이다.
하지만 위의 경우의 수밖에 없을까? 그렇지 않다.
포도주 N을 먹지 않는 경우의 수도 존재한다.
???? OOX
이런 수식이 있다고 했을 때, 당연히 최댓값은 DP(N-1) 일 것이다.
이 세 가지 경우중 가장 큰 것이 답이다.
이제 이것을 코드로 구현해 보겠다.
문제 구현 단계
#include <iostream>
using namespace std;
int d[10001];
int v[10001];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 1; i<= n; i++) cin >> v[i];
d[1] = v[1];
d[2] = v[1] + v[2];
for(int i = 3; i <= n; i++){
d[i] = max(d[i-3]+v[i-1]+v[i],d[i-2]+v[i]);
d[i] = max(d[i],d[i-1]);
}
cout << d[n];
}N-3부터 시작할 것이기 때문에 n이 1과 2일 때는 미리 처리해 준다.
그래서 1과 2일 때의 d값은 손수 계산해 줬다.
반복문을 사용하여 3부터 n까지 와인의 최댓값을 담는 배열 d와
와인의 점수를 담는 배열 v를 사용하여
3가지 경우의 수를 모두 비교하여 제일 큰 값을 도출했다.
그래서 마지막 n에 제일 큰 값이 저장될 것이기 때문에 그 값을 출력해 준다.
시행착오
전에 풀었던 계단 오르기 문제랑 비슷해서 쉽게 풀 수 있을 줄 알았다.
게다가 예제 케이스가 별로 없기도 하고 입력해 봤던 모든 값이 다 맞게 나와서 틀린 게 없는 줄 알았다.
근데 자꾸만 틀렸다고 나와서 애를 먹었다.
요인은 근본부터 틀리게 접근했던 것 같다.
나는 -1,-2까지밖에 안 갈 줄 알았는데
-3까지 갈 줄은 몰랐다. 그리고 이런 식으로 접근할 줄은 몰랐다.
DP는 항상 탑-다운 방식으로 풀었는데,
다운-탑 방식으로 풀어서 다양한 시각으로 봐야 할 것 같다.
여러 블로그를 참고해 보니까
탑 다운으로 푼 사람도 많던데 그냥 내가 생각이 짧은 것 같다.
좀 더 열심해해야 할 것 같다. 열받는다.