728x90
문제
접근 방식
가장 많은 양의 포도주를 마실 수 있는 경우를 찾아야 하는데
두 번째 조건을 보면 연속으로 마실 수 있는 포도주는 두 잔까지고
이는 1,2번째 잔을 마셨다면 3번째 잔은 건너뛰고
4,5,6,...n번째 포도주 중 하나를 먹어야 한다는 말이다.
거꾸로 생각해 보면 두 잔을 연속으로 마실 때는 이전 잔을 무조건 마셨다는 것이 되고
한 잔만 마셨을 때는 바로 이전 잔을 제외한 이전의 어떠한 잔들 중 하나 이상은 마신 것이 된다.
만약 n번째 잔을 마실 때, 해당 잔이 연속으로 두 번째 마시고 있는 잔이라면
(n번 잔의 양 + n-1번 잔을 첫 번째로 마신 경우의 최댓값) 이 해당 경우의 최댓값이 되고
해당 잔이 연속이 아닌 첫 번째로 마시고 있는 잔이라면
n-2 이하 번의 잔의 최댓값 + n번 잔의 양이 최댓값이 된다.
점화식을 정리하면 다음과 같다.
dp[n][한 잔을 연속으로 마신 경우] = dp[n-2][누적 최댓값] + n번 잔의 양
dp[n][두 잔을 연속으로 마신 경우] = dp[n-1][한 잔을 연속으로 마신 경우] + n번 잔의 양
dp[n][누적 최댓값] = max(dp[n-1][누적 최댓값], dp[n][한 잔을 연속으로 마신 경우], dp[n][두 잔을 연속으로 마신 경우])
풀이
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[] cups = new int[n + 1];
int[][] dp = new int[n + 1][3];
for (int i = 1; i <= n; i++) {
cups[i] = Integer.parseInt(br.readLine());
}
dp[1][0] = cups[1];
dp[1][2] = cups[1];
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i - 2][2] + cups[i];
dp[i][1] = dp[i - 1][0] + cups[i];
dp[i][2] = Math.max(dp[i - 1][2], Math.max(dp[i][0], dp[i][1]));
}
System.out.println(dp[n][2]);
}
}
'Java > Algorithms' 카테고리의 다른 글
| [백준] 2293번 : 동전 1 (0) | 2024.03.09 |
|---|---|
| [백준] 11052번 : 카드 구매하기 (0) | 2024.03.08 |
| [백준] 1904번 : 01타일 (0) | 2024.03.07 |
| [프로그래머스] 더 맵게 (0) | 2024.03.05 |
| [백준] 10994번 : 별 찍기 - 19 (0) | 2024.02.27 |
