알고리즘/DP
[JAVA] # 2156 포도주 시식
세댕댕이
2021. 9. 2. 13:17
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N;
static int[][] dp; // 0: 안마심 / 1: 1연속 마심 / 2: 2연속 마심
static int[] wine;
public static void print() {
for(int i = 0; i < N; i++) {
System.out.println(Arrays.toString(dp[i]));
}
System.out.println("----");
}
public static int func() {
// 초기화
dp[0][1] = wine[0];
// 메인
for(int i = 1; i < N; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][0] = Math.max(dp[i][0], dp[i - 1][2]);
dp[i][1] = dp[i - 1][0] + wine[i];
dp[i][2] = dp[i - 1][1] + wine[i];
//print();
}
// 출력
int ans = Math.max(dp[N - 1][0], dp[N - 1][1]);
return Math.max(ans, dp[N - 1][2]);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
dp = new int[N][3];
wine = new int[N];
for(int i = 0; i < N; i++) {
wine[i] = sc.nextInt();
}
System.out.println(func());
}
}dp 문제!
3번 연속으로 와인을 마실 수는 없기 때문에 dp[N][3] 배열을 이용해서 안마심 / 1연속 마심 / 2연속 마심
의 경우를 구분하여 최댓값을 구할 수 있도록 했다.
dp[i][0]의 경우, 두번 연속 이상으로 안 마시는 경우가 올 수도 있기 때문에 [0], [1], [2]중 최댓값을 넣어줘야 한다
*반례
6
1000
1000
1
1
1000
1000
----
이때 1, 1 구간에서 두번 연속 와인을 마시지 않아야 뒤에 1000, 1000을 둘 다 마실 수 있기 때문에 이 점을 반드시 고려해줘야함.
크게 어렵지는 않았다!
