1.
테이블 정의
•
첫째 줄에 포도주 잔의 개수 num이 주어진다
•
둘째 줄부터 num+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다
•
최대로 마실 수 있는 포도주의 양을 출력한다
규칙
•
연속으로 놓여 있는 3잔을 모두 마실 수는 없다
2.
점화식
dp[num] = Math.max(Math.max(recur(num-2), recur(num-3) + arr[num-1]) + arr[num], recur(num-1));
Java
복사
3.
초기값
dp[0] = 0;
dp[1] = arr[1];
if (num > 1) {
dp[2] = arr[1] + arr[2];
}
Java
복사
Top-down 방식으로 처리하였다
Python
import sys
sys.setrecursionlimit(10**6)
def recur(num):
if dp[num] is None:
dp[num] = max(max(recur(num-2), recur(num-3) + arr[num-2]) + arr[num-1], recur(num-1))
return dp[num]
if __name__ == "__main__":
num = int(input())
arr = [int(sys.stdin.readline()) for _ in range(num)]
dp = [None for _ in range(num+1)]
dp[0] = 0
dp[1] = arr[0]
if num > 1:
dp[2] = arr[0] + arr[1]
print(recur(num))
Python
복사
JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Integer[] dp;
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
dp = new Integer[num+1];
arr = new int[num+1];
for (int i = 1; i < num+1; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
dp[0] = 0;
dp[1] = arr[1];
if (num > 1) {
dp[2] = arr[1] + arr[2];
}
System.out.println(recur(num));
}
static int recur(int num) {
if (dp[num] == null) {
dp[num] = Math.max(Math.max(recur(num-2), recur(num-3) + arr[num-1]) + arr[num], recur(num-1));
}
return dp[num];
}
}
Java
복사