2156번:포도주시식(생각못했던 것)

Posted on Edited on In

생각못했던 것1

계단 오르기와 동일한 문제라고 생각했는데 차이가 있었다.

계단 오르기는 마지막 계단을 반드시 밟아야한다는 조건이 있었지만
포도주시식은 마지막 잔을 반드시 마셔야한다는 조건이 없었다.
즉, 포도주 시식의 경우, 마지막 잔을 안 마시는게 더 포도주를 많이 마실 수 있다면 그 경우를 찾아줘야한다.

가령 문제의 예시를 보면, 6잔의 포도주에
6 10 13 9 8 1 이 있을 때
기존의 계단오르기 처럼 하면
6 10 13 9 8 1 을 마셔 32를 최대라고 하는
6 10 13 9 8 1 이 경우가 33으로 최대이다.

잘못 짰던 코드 - 계단 오르기와 동일한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import collections

n = int(input())
wines = collections.defaultdict(int)
for i in range(1, n+1):
    wines[i] = int(input())

dp = collections.defaultdict(int)

<br>

# dp[i] = i번째를 반드시 마신다는 가정하에, i번째까지의 최대 와인 양
dp[1] = wines[1]
dp[2] = wines[1]+wines[2]
dp[3] = max(wines[1]+wines[3], wines[2]+wines[3])

for i in range(4, n+1):
    dp[i] = max(dp[i-2]+wines[i], dp[i-3]+wines[i-1]+wines[i])
print(dp[n])

위 원인을 반영한 코드 - 그래도 틀린 코드

dp[i] = max(dp[i-2]+wines[i],dp[i-3]+wines[i-1] + wines[i], dp[i-1])에서
dp[i-1]을 추가했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import collections

n = int(input())
wines = collections.defaultdict(int)
for i in range(1, n+1):
    wines[i] = int(input())

dp = collections.defaultdict(int)
# dp[i] = i번째를 마시든 안 마시든, i번째까지의 최대 와인 양
dp[1] = wines[1]
dp[2] = wines[1]+wines[2]
dp[3] = max(wines[1]+wines[3], wines[2]+wines[3])


for i in range(4, n+1):
    dp[i] = max(dp[i-2]+wines[i],
                dp[i-3]+wines[i-1] + wines[i], dp[i-1])
print(dp[n])

생각못했던 것2

dp[3]도 dp[2]와 비교해서 더 큰 값을 넣어줘야 했다.

최총 맞은 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import collections

n = int(input())
wines = collections.defaultdict(int)
for i in range(1, n+1):
    wines[i] = int(input())

dp = collections.defaultdict(int)
# dp[i] = i번째를 마시든 안 마시든, i번째까지의 최대 와인 양
dp[1] = wines[1]
dp[2] = wines[1]+wines[2]
dp[3] = max(wines[1]+wines[3], wines[2]+wines[3], dp[2])


for i in range(4, n+1):
    dp[i] = max(dp[i-2]+wines[i],
                dp[i-3]+wines[i-1] + wines[i])
    dp[i] = max(dp[i], dp[i-1])
print(dp[n])