[Python] 백준 2156. 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

DP문제. 점화식은 잘 구했는데, 점화식에 맞춰서 arr를 생성하는 과정에 또 시간소모가 심했다.

table[i] = i번째 위치에서 마실 수 있는 최댓값이라고 정의하면

• i-1번째와 i-2번째 둘 다 마신 경우 = i번째 위치를 마실 수 없으므로 table[i-1]
• i-1번째를 마시지 않은 경우 = table[i-2] + arr[i]
• i-2번째를 마시지 않은 경우 = table[i-3] + arr[i-1] + arr[i]

따라서 반복문을 순회할 때, i는 최소 3부터 시작해서 n만큼 순회해야 한다. 한다. table[i-3]이 존재해야 하기 때문.

그렇다는 건, 최초로 포도주 배열을 생성할 때, 앞부분 세 자리는 비어 있어야 한다는 뜻이다.