문제 출처 : https://www.acmicpc.net/problem/2156
이 문제를 해결하기 위해 다이나믹프로그래밍을 이용하였습니다. 포도주가 1잔인 경우 그것이 최대였고 포도주가 2잔인 경우에는 2잔 모두 마시는 것이 최대였습니다. 3잔부터는 다음과 같은 점화식이 생성됩니다.
n >= 3 인 경우 부터
dp[n] = Max(dp[n-1], dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n])
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.Math.max;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] wine = new int[n+1];
for(int i = 1; i <= n; i++){
wine[i] = Integer.parseInt(br.readLine());
}
int[] answer = new int[n+1];
answer[0] = 0;
answer[1] = wine[1];
if(n > 1){
answer[2] = wine[1] + wine[2];
}
for(int i = 3; i <= n; i++){
answer[i] = max(answer[i-1],max(answer[i-2]+wine[i],answer[i-3]+wine[i-1]+wine[i]));
}
System.out.println(answer[n]);
}
}