[BOJ 2156][백준 2156번] 포도주 시식 (파이썬 풀이)

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

2156번: 포도주 시식

 

🤔 문제 설명 및 입출력

---

 

✍ 접근 방법

---

"이번에 내가 포도주를 마시는게 이득인가? 아니면 존버했다가 다음에 마시는게 이득인가?" 라는 물음에 답할 수 있는 프로그램을 구현하는 것이 목표인 문제입니다.

 

언제 마시는게 최선의 선택이 되는지를 파악하려면 내가 여태까지 마신 와인의 상태를 저장하고 있어야합니다. 예를 들면 , N 번째 와인에 도달했을 때의 선택지는 아래와 같습니다

 

1. N-1번째 와인은 마셨는데 N-2번째 와인은 안 마셨다 ➡ N번째 와인을 마실 수 있다
2. N-2번째 와인은 마셨는데 N-1번째 와인은 안 마셨다 ➡ N번째 와인을 마실 수 있다
3. N-1번째 and N-2번째 와인을 안 마셨다 ➡ N번째 와인을 마실 수 있다
4. N-1번째 and N-2번째 와인을 마셨다 ➡ N번째 와인을 마실 수 없다.

 

그리디하게 생각해보면, 어쨌든 N번째 와인잔에 도달했을때 마시는게 이득이라고 생각이 듭니다. 그렇다면, N번째 와인을 마실 차례가 되었을때 항상 N번째 와인을 마실 수 있는 상태로 준비시켜놓는다면 어떨까요??

 

놓여진 와인을 주욱 보고 N-1번째 혹은 N-2번째 와인을 포기하더라도 ( 위 예시의 1,2번 선택지) N번째 와인을 마시거나 N-2번째 와인만 마시고 N번째 와인을 마시는 경우 중 더 큰 효용의 상태를 저장하면 어떨까요??

 

이 아이디어에 착안하여, max함수를 이용해 1,2,3 선택지 중 (4번은 앞서 말한 이유로 인해 제외합니다) N번째 와인을 마실때 가질 수 있는 최고값을 저장합시다.

 

 

👨‍💻 소스 코드

---

• 파이썬

N = int(input())
wine = [0,0,0]
memo = [0]*(N+3) # 먹은 와인을 저장하는 방법
for _ in range(N):
    wine.append(int(input()))
# index error 방지를 위한 dummy 값
wine.extend([0,0,0])

# index error 방지를 위해 3부터 시작,
# N번째 와인을 마실때 N-2번 와인잔도 조사하므로,  3부터 시작해야지 idx == 0 일때도 동작가능
for idx in range(3,N+3):
    memo[idx] = max(memo[idx-1],memo[idx-2]+wine[idx],memo[idx-3]+wine[idx-1]+wine[idx])

print(memo[-1])

 

 

🔥 강평

---

상태를 저장해야한다 ➡ 메모이제이션으로 해결 가능하다.

 

 

처음 아이디어를 도출하기는 어렵지만, 구현은 간단한 전형적인 콜롬버스 달걀형 문제라고 생각합니다.

 

저도 아직 DP가 익숙치 않은만큼 이 문제 풀 때 많이 골머리를 썩혔지만, 알고리즘이 항상 그렇듯, 비슷한 유형을 반복한다면 분명 정복 가능하리라 생각이 듭니다.