[Baekjoon Online Judge] 백준 2156번 포도주 시식(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2156번 포도주 시식

(C++, Python)

(글쓴날 : 2020.04.17)

 

---

* Baekjoon Online Judge, 백준 2156번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2156번 포도주 시식

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

n개의 포도주가 주어지고 연속으로 3잔 이상 마실 수 없을 때, 최대로 마실 수 있는 포도주의 양을 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

동적 계획법을 위해 도출한 점화식은 제 코드 기준으로

memoization[i - 3] + wines[i - 1] + wines[i]

or

memoization[i - 2] + wines[i]

or

memoization[i - 1]

입니다.

 

각각의 의미는

세 번째 전 포도주까지 마신 최대량 + 이전 포도주의 양 + 현재 포도주의 양,

두 번째 전 포도주까지 마신 최대량 + 현재 포도주의 양,

이전 포도주까지 마신 최대량

입니다.

 

특히, 마지막의 이전 포도주까지 마신 최대량을 생각해내는데 시간이 좀 걸렸는데,

6, 10, 13, 9 순으로 포도주가 있을 경우, 마지막 포도주를 마시지 않는 것이 최대로 마실 수 있는 포도주의 양입니다.

 

이후, 점화식을 이용한 반복문을 돌려 memoization을 통해 문제를 해결하였습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    cin >> n;
 
    vector<int> wines(n + 1, 0);
    for (int i = 1; i < n + 1; i++)
        cin >> wines[i];
 
    vector<int> memoization(n + 1, 0);
    int maxNum = 0;
 
    for (int i = 1; i < n + 1; i++)
    {
        if (i == 1)
        {
            memoization[1] = wines[1];
            continue;
        }
        if (i == 2)
        {
            memoization[2] = wines[1] + wines[2];
            continue;
        }
 
        maxNum = max(memoization[i - 3] + wines[i - 1] + wines[i], memoization[i - 2] + wines[i]);
        memoization[i] = max(maxNum, memoization[i - 1]);
    }
 
    cout << memoization[n];
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
n = int(input())
wines = [0] + [int(input()) for _ in range(n)]
memoization = [0] * (n + 1)
 
for i in range(1, n + 1):
    if i == 1:
        memoization[1] = wines[1]
        continue
    elif i == 2:
        memoization[2] = wines[1] + wines[2]
        continue
 
    memoization[i] = max(memoization[i - 3] + wines[i - 1] + wines[i], memoization[i - 2] + wines[i], memoization[i - 1])
 
print(memoization[-1])

---