S1 2156. 포도주 시식

문제 보기 :  2156번: 포도주 시식

---

문제

• 정답률 : 32%

---

작성 코드

T = int(input())
wine = [0]*(T+1)

for i in range(1,T+1):
    wine[i]=int(input())

cost = [0]*(T+1)

# wine = [0, 6, 10, 13, 9, 8, 1]
# cost = [0, 6, 16, 19, ...]

if T>=1:
    cost[1] = wine[1]
if T>=2:
    cost[2] = wine[1]+wine[2]
if T>=3:
    cost[3] = max(wine[1]+wine[2],wine[1]+wine[3],wine[2]+wine[3])

for i in range(4, T+1):
    cost[i] = max(cost[i-1], cost[i-2]+wine[i], cost[i-3]+wine[i-1]+wine[i])

print(cost[-1])

---

풀이

경우의 수를 따지면서 구해야하니 고려해야할 케이스가 많다고 생각했다.
즉, 1번 와인을 마셨다면 1번 와인만 마셨다/1,2번을 마셨다/1,3번을 마셨다가 나오는데 연쇄적으로 계속 케이스를 나누다보면 무한개의 경우가 나오기 때무네..

가장 적은 횟수로 구할 수 있는 방법은 4번을 먹게 된다면 1,2,3번 와인과 어떤 조합으로 마셨을 때 가장 많이 마실 수 있는지를 값으로 두는 것이었다. 

그리고 각각 1,2,3번 와인들도 앞서 등장한 와인 중 어떤 조합과 최대가 되는지를 계산해서 채워져있기 때문에 이 값을 활용하면 됐다.
그 부분이 아래를 나타낸다. (cost와 wine은 index 1이 시작점으로 두었다. 이거까지 통일 안되면.. 너무 헷갈려서)

for i in range(4, T+1):
    cost[i] = max(cost[i-1], cost[i-2]+wine[i], cost[i-3]+wine[i-1]+wine[i])

말로 설명하니 설명하기가 너무 어렵지만 ㅠㅠ 구현해보면 스스로 이해가 빨리 될 것 같다.