마지막 계단/포도주를 골라야 한다는 조건 빼고는 본질적으로 동일한 문제다
이 문제를 정확하게 이해하는데 이틀이 걸렸다..
계단 오르기를 예시로 들면
dp[i]=i번째 계단을 밟았을 때 얻을 수 있는 최대 점수
로 두고 점화식을 도출해본다
(각 계단에 적혀있는 점수는stairs[]
배열에 저장되어 있다)
e.g.
starts[]={10,20,15,25,10,20}
이고 1번 째부터 저장되어 있다
① dp[1]
=10
② dp[2]
=10+20
dp[1]와 dp[2]는 자명하다
③ dp[3]
= 10+15 / 20+15 => 20+15
3번 연속 계단을 밟을 수 없다는 조건 때문에 dp[3]
부터는 생각을 해보아야 한다.
i
번째 계단에 와서 밟았을 때,i-1
번째 계단을 밟는 것과,i-2
번째 계단을 밟는 경우로 생각할 수 있다.그렇다면 점화식이
dp[i]=max(dp[i-1], dp[i-2])+staris[i]
인가? 아니다
위의 그림과 같이 ⓐ,ⓑ 두 경우로 나타낼 수 있다
ⓑ 에서는 i-2
이 선택되지 않았다. dp[i-3] (i-3번째까지 밟았을 때 얻을 수 있는 최대 이익)
에 이전 계단, 현재 계단을 밟은 값을 더해준다.
(dp[i-1]
에 저장된 값이 i-2
를 밟고 얻은 최적해인지 i-2
를 밟지 않고 얻은 최적해인지는 모른다)
즉 dp[i-3]에 staris[i-1]과 staris[i]
를 더해준다
ⓐ 에서는 i-2
가 선택되었다. 즉 i-2
를 고른다는 뜻은 i-2
지점에서 얻을 수 있는 최대점수 dp[i-2]
를 고른다는 뜻이다.
따라서 ⓐ의 경우는 dp[i-2]+staris[i]
이다.
전체코드
#include <iostream> #include <vector> using namespace std; const int MAX = 301; int N; vector<int> stairs; int cache[MAX]; void dp() { cache[1] = stairs[1]; cache[2] = stairs[1] + stairs[2]; for (int i = 3; i <= N; i++) cache[i] = max(cache[i - 3] + stairs[i - 1] + stairs[i], cache[i - 2] + stairs[i]); cout << cache[N] << endl; } void input() { cin >> N; stairs = vector<int>(N+1); for (int i = 1; i <= N; i++) cin >> stairs[i]; } int main() { input(); dp(); return 0; }
다음으로 포도주 시식의 경우, 마지막 포도주를 꼭 마셔야한다는 내용이 없다. 따라서 위에서 max값을 비교할 때, dp[N-1]의 경우를 하나 더 추가해준다.
전체코드
#include <iostream> #include <vector> #include <algorithm> using namespace std; int N; vector<int> glass; vector<int> dp; void solution() { dp[0] = 0; dp[1] = glass[1]; dp[2] = glass[1]+glass[2]; for (int i = 3; i <= N; i++) { dp[i] = max({ dp[i - 2] + glass[i], dp[i - 3] + glass[i - 1] + glass[i], dp[i - 1] }); } cout << dp[N] << endl; } void input() { cin >> N; glass = vector<int>(N+1); dp = vector<int>(N + 1); for (int i = 1; i <= N; i++) cin >> glass[i]; } int main() { input(); solution(); return 0; }