포도주 시식 (실버 1)

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

2156번: 포도주 시식

 

---

 

문제 접근

 

최대한 많은 양의 포도주를 선택해야 하는 문제이다.

 

최대의 양을 마셔야 하는 조건,  포도주를 3개 연속 선택할 수 없는 요구조건을 보았을 때 이전 풀었던 "계단 오르기"의 다른 버전이라고 생각했다. 

 

계단 오르기는 dp 테이블의 요소와 문제의 리스트를 모두 활용하여 최대값일 경우 선택하여 dp 테이블을 채우는 알고리즘을 사용했었다.

 

그것을 힌트로 문제에 접근하여 보았다.

 

키워드

dp table

bottom - up

dp 테이블 요소를 다시 활용

 

 

직접 손으로 그려가며 패턴을 찾기위해 n = 1 , n = 2 , n = 3 , n = 4 일 경우를 생각해 보았다.

---

 

 

 

포도주의 정보가 들어 있는 리스트 : podo

dp 테이블 : dp

 

n = 1  

n = 2 

 

이 경우를 base case로 설정,

 

n = 3  일 경우부터 모든 경우의 수를 생각해 보았다.

 

 

총 3 가지의 경우의 수가 나왔고 이 3 가지 경우의 수 중 가장 큰 값을 dp [i]로 설정하는 방법을 설계하였다.

 

하지만, 이 경우는 단순히 n = 3 일 경우에만 해당된다. n = 4 이상일 경우에는 성립하지 않게 된다. 

 

 

dp 테이블의 요소를 다시 활용하면, 이전의 값을 활용하여 총 3가지의 경우의 수가 나왔다.

 

 

모든 경우의 수를 구하였으니, dp 테이블을 구하는 로직을 구현하면 된다.

 

---

 

구현

 

 

# 1월 5일 금요일

# dp 포도주 시식 실버1

# bottom - up 방식

n = int(input())

podo = []
dp = [0] * n

for _ in range(n):
    podo.append(int(input()))

if n >= 3:
    dp[0] = podo[0]
    dp[1] = podo[0] + podo[1]  # base case 작성
    for i in range(2, len(podo)):
        a = dp[i-1]
        b = dp[i-2]+podo[i]
        c = dp[i-3]+podo[i-1]+podo[i]
        dp[i] = max(a, b, c)

    print(dp[-1])

elif n == 1:
    print(podo[0])
elif n == 2:
    print(podo[0]+podo[1])

 

3가지의 경우의 수를 디버그 하기 쉽게 각각 a, b, c 변수에 할당해 주었다.

 

처음에는 n이 2 이하일 경우의 예외처리를 하지 않아 인덱스 에러가 생겼었다. 항상 주의하자

 

---

 

느낀 점 및 배운 점

 

1. 이전 풀었던 dp와 다른 점을 생각해 보았다.

 

모든 경우의 수를 생각해야 하는 것 + dp 테이블을 다시 확인하여 점화식을 도출해 내는 능력

 

 

계단 문제를 생각해 내었다는 점에서, 이전 공부가 확실히 되었다는 것 또한 체감할 수 있었던 문제였다.