[BOJ/Step15] 2156 : 포도주 시식 (Python)

www.acmicpc.net/problem/2156

2156번: 포도주 시식

---

2579 : 계단 오르기 문제랑 똑같이 풀면 된다

대신 계단은 마지막 계단을 꼭 밟아야 하지만 마지막 포도주를 마실 필요는 없기 때문에

맨 마지막 포도주의 최종 양이 아닌 리스트 중 최댓값을 출력해주면 된다

 

라고 생각했는데 이게 웬걸

대뜸 틀려버려서 뭐가 틀린건지 찾아봤는데

아니 n번째 포도주를 마시는데 대체 왜 n번째 포도주를 마시지 않는 경우가 고려사항에 포함된단 말인가?

세상에나 1도 이해 안가네 ...

 

그래서 백준에 질문을 올렸는데 댓글로 반례를 알려주심

# 2156.PY

n = int(input())

grape = [int(input()) for _ in range(n)]
t_grape = [0 for _ in range(n)]

t_grape[0] = grape[0]

if n > 1:
    t_grape[1] = grape[0] + grape[1]
if n > 2:
    t_grape[2] = grape[2] + max(grape[0], grape[1])

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

print(max(t_grape))

이렇게 풀었는데 포도주 6잔 100 100 1 1 100 100 을 입력하면 답은 400인데 내 코드는 301이 나온다..

 

뭐가 문제인고 보니까 포도주를 두잔 뛰어넘을 수 있는데 내 코드는 무조건 하나만 뛰어넘는게 되는것이다

n번째 총합 = n번째 양 + max( n-1번째 양 + n-3번째 총합, n-2번째 총합 )이기 때문에

중간에 두개를 건너뛰면 그 경우를 계산할 수가 없다

그래서 중간에 두개 건너뛰는 경우를 추가해서

# 2156.PY

n = int(input())

grape = [int(input()) for _ in range(n)]
t_grape = [0 for _ in range(n)]

t_grape[0] = grape[0]

if n > 1:
    t_grape[1] = grape[0] + grape[1]
if n > 2:
    t_grape[2] = grape[2] + max(grape[0], grape[1])

for i in range(3, n):
    t_grape[i] = grape[i] + max(t_grape[i-2], grape[i-1] + t_grape[i-3], grape[i-1] + t_grape[i-4])

print(max(t_grape))

n번째 총합 = n번째 양 + max( n-2번째 총합, n-1번째 양 + n-3번째 총합, n-1번째 양 + n-4번째 총합 )

으로 두개 건너뛰는 경우를 추가해주었다

그랬더니 정답!

 

사실 맞긴 했는데 n번째 포도주를 안마시는 경우를 추가한 거랑 어떤식으로 다르고

n번째 포도주를 안마시는 경우는 어떻게 맞는건지 좀.? 이해가 안가긴 한다

그냥 무조건 최댓값 구하는 거니까 그걸 더하나.?

근데 그럼 n번째는 결국 안마신건데 뒤에 계산할 때 연속해서 마시는걸 확인하기가 어렵지 않나... 모르겠다 ㅜ

암튼 난 이렇게 풀었음

 

사실 세개 네개 다섯개 건너뛰는 경우도 있을거 같기는 한데 모르겠다 그땐 어떻게 해야되는지

문제에 몇개 건너뛸 수 있는지 나오면 좋을텐뎅