[ BOJ 오답노트 ] 2156 파이썬 : 포도주 시식

2022 03 30

1. 틀린 기록

 

 

 

2. 원인 분석

- 아니 자꾸 '틀렸습니다'라는 결과만 나왔다.

- 질문게시판의 반례들을 찾아보는 와중에 틀린 부분을 찾을 수 있었다.

 

[ 수정 전 ]

n = int(input())
drink = [0]
dp = [0]*(n+1)

for _ in range(n):
    drink.append(int(input()))

if n == 1:
    print(drink[1])
else:
    dp[1] = drink[1]

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

    print(max(dp))

 

반례 출처 : https://raejoonee.tistory.com/15

- 나머지 testcase에서는 올바른 답이 나왔지만, 위의 두가지 예시에서는 오답이 나왔다.

- 내가 수정 전 코드에서 고려한 것은 두가지였다.

- 이렇게 하면 아래의 예제에서 다음과 같이 도출된다.

n = 6 / 1000 1000 1 1 1000 1000

 

답 : 4000

내 코드 답 : 3001

 

- 따라서 drink[n - 1]과 dp[n - 3]을 같이 뽑는 경우가 아니라, dp[n - 3]만을 뽑는 경우가 필요하다.

 

- 그러면 위의 예제에서

답 : 4000

 

 

 

3. 해결

n = int(input())
drink = [0]
dp = [0]*(n+1)

for _ in range(n):
    drink.append(int(input()))

if n == 1:
    print(drink[1])
elif n == 2:
    dp[1] = drink[1]
    dp[2] = drink[1] + drink[2]

    print(dp[2])
elif n == 3:
    dp[1] = drink[1]
    dp[2] = drink[1] + drink[2]
    dp[3] = max(dp[1], drink[2] + dp[0]) + drink[3]

    print(max(dp))
else:
    dp[1] = drink[1]
    dp[2] = drink[1] + drink[2]
    dp[3] = max(dp[1], drink[2] + dp[0]) + drink[3]

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

    print(max(dp))

 

 

 

4. 배운 점

- 일단 이번 문제는 계단 오르기 문제 (2579번) 풀이를 생각하면서 해결했다.

- 하지만 생각하지 못했던 반례가 있었다. 앞으로 반례를 계속 생각해야겠다. 실제 코테 시험에서는 다른 사람의 반례를 참고할 수 없으므로..