[C++] 백준 2156번 : 포도주 시식 (S1)

#문제

www.acmicpc.net/problem/2156

2156번: 포도주 시식

#풀이 & 학습한 내용

supremo7.tistory.com/88에서 푼 이친수 문제와 유사한 문제이다. 이 문제는 경우를 크게 3가지로 나눠 문제를 관찰했다. 마신것을 1, 안마신것을 0이라 할 때, i-1번째와 i번째의 경우를 ?0,01,11로 나누었다.(?0은 00과 10을 모두 포함한다) 이때, 각각의 경우를 dp배열의 index 0, 1, 2에 저장하여 각각의 optimization을 관찰했다. dp[i][1]는 "index1상황에서 i번째 포도주까지의 최대량"으로 정의했다. dp[i][0],dp[2]도 index상황만 바꾸어 같게 정의했다.그리고 소스코드의 19~21행의 optimal substructure를 통해 dp배열을 n까지 채워나갔다. 그리고 답으로 dp[n][0],dp[n][1],dp[n][2] 중 최댓값을 출력해줬다.

dp배열을 1차원으로 선언해서 dp[i] = max(dp[i-1], dp[i-2]+p[i], dp[i-3]+p[i-1]+p[i])로 optimal substructure를 정의할 수도 있다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int p[10002];
int dp[10002][3];
 
int main(void) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
 
    dp[1][0] = 0; dp[1][1] = p[1]; dp[1][2] = 0;
 
    for (int i = 2; 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] + p[i];
        dp[i][2] = dp[i - 1][1] + p[i];
    }
    cout << max({ dp[n][0],dp[n][1],dp[n][2] }) << '\n';
    
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_2156.cpp

HoYoungChun/BOJ_algorithm