포도주
case1 :
dp[i] = dp[i-1];
// arr[i]를 선택하지 않는 경우 이전 계산값중 최대값을 선택함.
//위의 연산으로 dp[i]는 항상 dp테이블 중 최대값으로 설정된다.
case2 :
//일반적인 경우로 바로 직전의 dp값은 연속된 경우를 포함하므로 사용 불가.
//직전 포도주를 마시지 않은 경우, dp[i-2]가 최대값.
//직전 포도주를 마신 경우, dp[i-2]와 3연속이 되므로 dp[i-3]를 선택하는 것이 최대값.
long temp = Math.max(dp[i - 2], arr[i - 1] + dp[i - 3]) + arr[i];
dp[i] = Math.max(dp[i], temp) ;
ex)
3
15 30 1
1 15
2 45
3 45
45
import java.util.Scanner;
class Main {
static int N;
static long[] dp;
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
long [] arr = new long[10001];
dp = new long[10001];
long max = 0;
for (int i = 1; i <= N; ++i)
arr[i] = in.nextInt();
dp[1] = arr[1];
dp[2] = arr[1] + arr[2];
for (int i = 3; i <= N; ++i) {
//version 1 : 포도주를 마시지 않는 경우가 고려되지 않음..
//반례
// 3
// 15 30 1 version 1 계산식에 따르면 dp[3]=31이 된다. 하지만 3번을 마시지 않는 경우 정답은 45가 된다.
// 45
// 먼저 dp[i]를 이전 최대값으로 설정 arr[i] 포도주를 마시지 않는 경우 ( i번째를 선택하지 않는 경우를 고려..)
// 그리고 포도주를 마셔 계산된 값과 비교한다.
dp[i] = dp[i-1];
long temp = Math.max(dp[i - 2], arr[i - 1] + dp[i - 3]) + arr[i];
dp[i] = Math.max(dp[i], temp) ;
}
for ( int i = 1 ; i <= N ; ++i) System.out.printf("%d %d\n", i , dp[i]);
System.out.println(dp[N]);
}
}
ex) 반례
3
15 30 1
1 15
2 45
3 45
45
ex)
6
6
10
13
9
8
1
1 6
2 16
3 23
4 28
5 33
6 33
33
