백준 2156번 포도주 시식(와인 시음)

문제 링크

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

풀이 전 계획과 생각

처음에 이 문제가 혼란스러웠던 점은 2579번 계단 오르기와 동일한 내용의 문제라고 오해한 점에 있었다.

2579번 계단 오르기 문제에서도 연속으로 세 개의 계단을 밟을 수 없다는 점이 동일하기 때문이다.

그런데 아주 중요한 다른 점이 있다.
계단 오르기 문제에서는 연속으로 세 개의 계단을 밟을 수 없지만 점프도 한 계단만 할 수 있다. 그래서 두 개의 계단을 밟은 뒤에는 반드시 한 번 점프를 하고 다음 계단을 밟는다.
그런데 2156번 와인 시음회('포도주시식'이라고 해서 딴 거 말하는 줄 알았잖아! 띄어쓰기도 안 하고! ㅋㅋㅋ) 문제에서는 계속 안 마실 수가 있다.
계속 안 마시면 최댓값이 늘어나지 않는데 어떻게 하냐고?
이런 경우가 있다.

• 입력값이 6 100 100 1 1 100 100이다.
• 즉 와인 시음 자리가 총 6개이고 각각의 자리의 와인의 양은 100 100 1 1 100 100이다.
• 세번째 자리의 최댓값은 무엇일까? 첫번째 두번째 세번째를 다 마실 수는 없다. 그러면 세번째와 첫번째, 세번째와 두번째를 마시는 걸 생각할 수 있는데, 뿐만 아니라 그냥 첫번째 두번째만 마시고 세번째를 안 마셔도 된다. 그래서 세번째 자리의 최댓값은 101이 아니고 200이다.
• 네번째는 처음의 100 둘을 다 마셔도 3연속이 되지 않으니까 최댓값은 201이다.
• 다섯번째에서는 앞의 두 개의 100을 먹어야 최댓값이 나온다. 그러니까 세 번째 1을 스킵하면 네 번째 1과 다섯 번째 100은 먹을 수 있다. 그래서 최댓값이 301이다.
• 여섯번째의 경우 네 번째 1을 먹으면 다섯 번째와 여섯 번째의 100과 3연속이 발생하기 때문에 네 번째 1을 안 먹어야 한다. 그리고 첫번째와 두번째의 100을 모두 먹기 위해서는 세번째의 1을 안 먹어야 한다. 이렇게 두 번을 모두 안 마셔야 하는 경우를 고려하지 않으면 엉뚱한 결과가 나올 수 있다.
• (세 번 연속을 안 마시는 경우는 고려할 필요가 없는 것 같다. 직전과 직후에 큰 값이 있는 경우 두 번 연속으로 작은 값이 있으면 그 둘 중 하나라도 먹으면 직전 직후의 큰 값을 못 먹게 되지만, 세 번 연속으로 작은 값이 있는 경우는 첫번째와 세번째만 안 먹으면 되고 가운데의 작은 값은 먹어도 된다. 직전 직후와 3연속이 발생하지 않으니까.)

아무튼 처음에는 정말 답답하게 느껴졌지만 나의 경우는 현재를 아예 안 먹고 직전까지만 최댓값을 계산하는 경우를 최댓값에 포함하니 해결되었다.

풀이 (코드 블록 첨부)

import sys
def wine(n,amount,total):
    current_max = amount[0]
    if n==1:
        return current_max
    total[0]=current_max
    current_max=amount[0]+amount[1]
    if n==2:
        return current_max
    
    total[1]=current_max
    
    current_max = max(amount[2]+amount[1], amount[2]+amount[0],total[1])
    if n==3:
        return current_max
    total[2]=current_max
    for i in range(3,n):
        
 
        total[i]=max(amount[i]+total[i-2],amount[i]+amount[i-1]+total[i-3], total[i-1])
        if current_max<total[i]:
            current_max=total[i]
    #print(total)
    return current_max
        # 현재를 안 마시고 직전 두 개를 마시는 게 최댓값인 경우가 있음
        
# 반례 10 0 0 10 0 5 10 0 0 1 10 정답 36
# 반례 6 100 100 1 1 100 100 정답 400
# 반례 9 6 10 13 9 8 1 1 2 4 정답 39
# 반례 7 100 100 1 1 1 100 100 정답 401
# 반례 6 1000 1000 1 1 1000 1000 정답 4000
# 반례 7 5 0 2 0 9 3 0 정답 19
# 반례 6 999 999 1 1 999 999 3996
# 반례 7 1 10 1 10 1 10 1 정답 32
# 반례 4 0 1000 1000 0 정답 2000
# 반례 3 3 2 1 정답 5
N = int(sys.stdin.readline())
amount_arr=[int(sys.stdin.readline()) for x in range(N)]
#amount_total_arr = [[0,0] for x in range(N)]
amount_total_arr = [0 for x in range(N)]
#print(amount_total_arr)
print(wine(N,amount_arr,amount_total_arr))

#print(amount_arr)
# 첫번째 잔 최댓값: 첫번째 잔
# 두번째 잔 최댓값: 첫번째 잔+두번째 잔
# 세번째 잔 최댓값: max(세번째 잔+두번째 잔,세번째 잔+첫번째 잔, 두번째 잔+첫번째 잔)
# 다음 잔 최댓값: max(현재 잔+전전 잔 최댓값, 현재 잔+직전 잔+전전전 잔 최댓값, 직전 잔 최댓값)

풀이하면서 막혔던 점과 고민

안 마신 경우를 최댓값에 포함해야 한다고 해서 눈앞이 캄캄했는데 그냥 현재를 안 마시고 직전과 전전을 다 마시는 경우를 현재의 최댓값으로 반영시키니까 무난하게 해결되었다. 사실 이 문제에서는 안 마시는 건 두 번까지만 할 수 있게 하면 된다. 1000 1000 1 1 1000 1000인 경우는 세 번째와 네 번째를 아예 안 마셔야 나머지 네 개의 1000을 다 먹을 수 있는데 1000 1000 1 1 1 1000 1000인 경우는 네 번째의 1은 먹어도 3연속이 발생하지 않는다.

풀이 후 알게된 개념과 소감

비슷해 보이는 문제라도 방심하지 말고 잘 살펴봐야겠다. ㅋㅋㅋ
다행히 반례를 미리미리 확인해서 잘못된 코드를 제출하지 않고 무사히 한번에 합격했다.

지금까지는 합격을 해도 간신히 시간 초과만 면하는 수준이었는데 이번에는 최근 제출 목록 중 시간복잡도도 상위권(?)이라서 더욱 뿌듯하다. ㅋㅋㅋ