2156. 포도주 시식

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

2156번: 포도주 시식

 

최대로 마실 수 있는 포도주의 양을 구해야 한다.

각 포도주잔에 포도주가 얼마나 있는지 나와있고 연속으로 3잔을 마실수는 없다.

 

Solution

 

1차원 다이나믹

 

d[n] : n번째 잔 까지 최대로 마실수 있는 포도주의 양

a[n] : n번째 잔에 들어있는 포도주의 양

 

두 번째 인덱스를 "n번째 잔에서 연속으로 마신 잔의 수" 라고 하면

d[n][0] : n번째 잔을 마시지 않는다

d[n][1] : n번째 잔을 1번 연속으로 마신다

d[n][2] : n번째 잔을 2번 연속으로 마신다

 

 

그렇다면 d[n]은 n 번째 잔까지 최대로 마실수 있는 포도주의 양 이므로

위에 세 상황 중에 가장 큰 값이 d[n]이 된다고 할 수 있다. 

d[n] = max(d[n][0], d[n][1], d[n][2])

 

 

d[n][0]

n번째 잔을 마시지 않는 상황.

그러므로 바로 전 단계에서 포도주를 마셨건 안 마셨건 상관이 없다.

d[n][0] = max(d[n-1][0], d[n-1][1], d[n-1][2])

 

d[n][1]

n번째 잔을 1번 연속으로 마시는 상황.

그렇다는 것은 바로 전 단계에서는 안 마셨어야 된다는 것.

d[n][1] = d[n-1][0] + a[n] 

 

d[n][2]

n번째 잔을 2번 연속으로 마시는 상황.

그렇다는 것은 바로 전 단계에서 1잔을 마신 상황이어야 한다. 

d[n][2] = d[n-1][1] + a[n]

 

위 세 가지 값 중 가장 큰 값이 d[n]이 된다.

 

d = [[0] * 3 for i in range(10001)]
a = [0] * 10001

n = int(input())
for i in range(1, n+1): a[i] = int(input())

# 첫 번째 잔
d[1][0] = 0
d[1][1] = a[1]
d[1][2] = a[1]

for i in range(2, n+1):
    # n번째 잔을 마시지 않는 상황
    d[i][0] = max(d[i-1][0], d[i-1][1], d[i-1][2])
    # n번째 잔을 연속으로 1잔 마시는 상황
    d[i][1] = d[i-1][0] + a[i]
    # n번째 잔을 연속으로 2잔 마시는 상황
    d[i][2] = d[i-1][1] + a[i]

print(max(d[n][0], d[n][1], d[n][2]))

 

---

1차원 다이나믹

 

d[n] : n번째 잔 까지 최대로 마실수 있는 포도주의 양

n번째에서 안 마신 상황, 1번 연속으로 마신상황, 2번 연속으로 마신 상황은 동일.

 

n번째에서 안마신 상황

n번째에서 안 마신 상황이기 때문에 n-1번째에서 마셨던 안 마셨던 상관이 없다.

그 말은 즉 n번째 값이 n-1번째 값과 동일하다는 것이다.

d[n] = d[n-1]

 

n번째에서 1번 연속으로 마신 상황

n번째에서 1번 연속으로 마시려면 n-1번째에서 안 마셨어야 가능하다.

그런데 생각해보면 n-1번째에서 안 마셨다는 것은 즉 (위와 동일하게) n-1번째 값이 n-2번째 값과 동일하다는 것이다.

d[n] = d[n-2] + a[n]

 

n번째에서 2번 연속으로 마신 상황

n번째에서 2번 연속으로 마신 상황이 되려면 

n-1번째에서 마셔야 하고, n-2번째에서는 안 마셔야 한다.

위 와동 일하게 n-2번째에서 안 마셨다면 n-3번째 값과 같다.

d[n] = a[n-1] + a[n] + d[n-3]

 

d = [0] * 10001
a = [0] * 10001

# inputs
n = int(input())
for i in range(1, n+1): a[i] = int(input())

# base
d[1] = a[1]
d[2] = a[1] + a[2]

for i in range(3, n+1):
    d[i] = max(d[i-1], d[i-2] + a[i], d[i-3] + a[i] + a[i-1])

print(d[n])

 

---

이 문제는 결국 혼자 못 풀고 솔루션을 보고야 알았다..

솔루션을 보고 어떻게 풀었는지 이해는 가지만 또 비슷한 문제가 나왔을 때 풀 수 있을까? 라는 느낌.

아직 dp를 푸는 법을 제대로 모르겠다.

문제를 더 많이 풀어봐야 감이 딱 올 것 같다.