문제

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

풀이방법

• 매 술잔을 선택할 때 3가지 경우의 수를 고려하여 가장 높은 값을 저장한다.
• 첫 번째 경우는 현재선택한 잔을 마시지 않는 것이다.
• 두 번째 경우는 현재와 다음 잔을 연속으로 마시는 것이다.
• 세 번째 경우는 현재 선택한 잔 한잔만 마시는 것이다.
• 이대로 문제풀이만 하면 정답은 무조건 나온다.

첫 코드

• 시간복잡도를 고려하지 않아 시간초과 발생

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n=int(input())
arr=[0]*n
for i in range(n):
    arr[i]=int(input())

vals=[0]*n

def find(idx):
    if idx>=n:
        return 0
    
    if vals[idx]==0:
        if idx+1==n:
            vals[idx]=arr[idx]
        else:
            vals[idx]=max(find(idx+1), arr[idx]+find(idx+2), arr[idx]+arr[idx+1]+find(idx+3))
    
    return vals[idx]

print(find(0))

정답 풀이방법

• 하향식 풀이방법을 사용하여 재귀함수를 사용하지 않음

import sys
input=sys.stdin.readline
n=int(input())
arr=[0]*n
for i in range(n):
    arr[i]=int(input())

vals=[0]*n

if n==1:
    vals[0]=arr[0]
elif n==2:
    vals[0]=arr[0]+arr[1]
else:
    vals[0]=arr[0]
    vals[1]=arr[0]+arr[1]
    vals[2]=max(vals[1], arr[0]+arr[2], arr[1]+arr[2])

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

print(max(vals))