[백준][dp] 2156 포도주 시식 c++구현

목차

https://www.acmicpc.net/problem/2156

문제

 

문제 구현 방향

쌓인 것을 기준으로 이차원 배열을 누적해서 풀었다.

쌓인 것이 0, 1, 2 를 기준으로 각각에 맞게 그전거에 누적해서 풀어주면 된다.

처음에는 그냥 담고 안담고를 세어주는 식의 브루트 포스를 했는데 메모리 초과가 나니 잘못된 방법이다.

 

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;

int n;
int arr[10001] = { 0 };
int dp[10001][3] = { -1 };


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    dp[0][0] = 0;
    dp[0][1] = arr[0];

    for (int i = 1; i < n; i++) {
        int newNum;
        int newCnt;

        for (int j = 0; j < 3; j++) {
            if (j == 0) {
                dp[i][j] = max({ dp[i - 1][0], dp[i - 1][2], dp[i - 1][1] });
            }
            else if (j == 1) {
                dp[i][j] = max(dp[i - 1][j - 1] + arr[i], dp[i - 1][j]);
            }
            else {
                dp[i][j] = max({ dp[i - 1][j - 1] + arr[i], dp[i - 1][j], dp[i - 1][j - 2] + arr[i] });
            }

        }
    }
    cout << max({ dp[n - 1][0], dp[n - 1][1] , dp[n - 1][2] });
    
   
    return 0;

}

 

일차원 배열을 통한 풀이

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;



int N;
int arr[10001] = { 0 };
int dp[10001] = { 0 };
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    dp[0] = arr[0];
    dp[1] = arr[0] + arr[1];
    dp[2] = max({ dp[1] ,arr[0] + arr[2], arr[1] + arr[2] });
    for (int i = 3; i < N; i++) {
        dp[i] = max({ dp[i - 1], dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1] });
    }
    cout << dp[N - 1];
    return 0;
   

}

점화식을 통해 다시 풀어 보았다..