백준 2156번, 포도주 시식 JAVA풀이
- 포도주가 일렬로 놓여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 함
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
D[i][j] = A[1] ~ A[i] 포도주A[i] : i번째 잔의 양- i번째 잔 : 연속 j 번
- 0번 연속 :
D[n][0] = max(D[n-1][0], D[n-1][1], D[n-1[2]) - 1번 연속 :
D[n][1] = D[n-1][0] + A[n] - 2번 연속 :
D[n][2] = D[n-1][1] + A[n] D[i] = A[1], ... , A[i] 까지 포도주를 마셨을 때, 마실 수 있는 포도주의 최대 양- 0번 연속해서 마신 포도주 :
A[i] 를 마시지 않음 - 1번 연속해서 마신 포도주 :
A[i-1] 를 마시지 않음 - 2번 연속해서 마신 포도주 :
A[i-1] 을 마시고, A[i-2] 는 마시지 않았어야 함 - 0번 연속 :
D[n-1] - 1번 연속 :
D[n-2] + A[n] - 2번 연속 :
D[n-3] + A[n] + A[n-1]
static int[] a = new int[10003];
static int[] dp = new int[10003];
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
for (int i=1; i<=n; i++) {
a[i] = fs.nextInt();
}
dp[1] = a[1];
dp[2] = a[1] + a[2];
for (int i=3; i<=n; i++) {
dp[i] = dp[i-1];
if (dp[i] < dp[i-2] + a[i]) {
dp[i] = dp[i-2] + a[i];
}
if (dp[i] < dp[i-3] + a[i] + a[i-1]) {
dp[i] = dp[i-3] + a[i] + a[i-1];
}
}
System.out.println(dp[n]);
}
