포도주는 연속으로 세 잔 마실 수 없다
이 말을 다시 생각해보면 n 번째 포도주의 경우의 수가 3가지가 나온다.
- n 번째 포도주를 안마신다.
- n 번째 포도주를 연속되지 않게 처음으로 마신다.
- n 번째 포도주를 연속되게 마신다.
그러면 n개의 포도주에서 최대한 많은 양을 마시는 방법은
1 + 2 + 3 방법들 중 선택했을 때 누적합이 가장 큰 방법을 선택하는 것이다.
그러면 일단 dp 배열을 생성하자
dp[n][0] : n 번째 포도주를 안마신다는 뜻이다.
dp[n][1] : n 번째 포도주를 연속되지 않게 처음으로 마신다.
dp[n][2] : n 번째 포도주를 연속되게 마신다.
즉, int[][] dp = new int[N + 1][3] 로 생성하면 된다.
그 다음으로 각각의 경우일 때 마다 누적합을 구해보자
0 : n 번째 잔을 안마신다
1 : n 번째 잔을 처음으로 마신다
2 : n 번째 잔을 연속으로 두번째로 마신다각각의 경우의 그 전 포도주의 상태를 생각해보면 된다.
dp[n][0] = Math.max(dp[n-1][0], dp[n-1][1], dp[n-1][2])
: n 번째 포도주를 안마시면 n-1 번째 포도주는 모든 상황이 될 수 있으므로 모든 상황에서 가장 누적합이 큰 상황을 고른다.
dp[n][1] = dp[n-1][0] + quantity[n]
: n 번째 포도주를 연속되지 않게 처음으로 마실려면 n-1 번째 포도주는 안마신 상태여야 한다. 그리고 n 번째 포도주를 마셨으므로 n 번째 포도주의 양을 더해준다.
dp[n][2] = dp[n-1][1] + quantity[n]
: n 번째 포도주를 연속되게 마시려면 n-1 번째 포도주를 처음으로 마신 상태여야 한다. n-1 번째 포도주를 안마시거나 연속되게 마셨으면 이는 성립하지 않는다. 즉, n-1 번째 포도주를 처음으로 마신 상태의 누적합과 n 번째 포도주를 마셨으므로 n 번쨰 포도주의 양을 더해준다.
public class bj2156 {
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 포도주의 정보들을 입력 받는다.
int N = Integer.parseInt(br.readLine());
int[] quantity = new int[N + 1];
for (int i = 1; i < N + 1; i++) {
quantity[i] = Integer.parseInt(br.readLine());
}
// 0 : n 번째 잔을 안마신다
// 1 : n 번째 잔을 처음으로 마신다
// 2 : n 번째 잔을 연속으로 두번째로 마신다
int[][] dp = new int[N + 1][3];
// dp[n][0] = Math.max(dp[n-1][0], dp[n-1][1], dp[n-1][2])
// dp[n][1] = dp[n-1][0] + quantity[n]
// dp[n][2] = dp[n-1][1] + quantity[n]
dp[1][0] = 0;
dp[1][1] = quantity[1];
for (int i = 2; i < N + 1; i++) {
dp[i][0] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
dp[i][1] = dp[i - 1][0] + quantity[i];
dp[i][2] = dp[i - 1][1] + quantity[i];
}
int answer = Math.max(Math.max(dp[N][0], dp[N][1]), dp[N][2]);
bw.write(answer + "\n");
bw.flush();
bw.close();
br.close();
}
}