이 문제는 전형적인 DP 문제이다.
문제를 푸는 팁은 포도주는 최대 3개까지만 연속으로 마실 수 있기 때문에 점화식에서 d[i-1], d[i-2]+amount[i], d[i-3]+amount[i-1]+amount[i] 중 최댓값을 구하여 d[i]에 넣어주어야 한다는 것이다.
그래서 정답 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] amount = new int[n + 1];
int[] d = new int[n + 1];
for (int i = 1; i <= n; i++) {
amount[i] = Integer.parseInt(br.readLine());
}
d[0] = 0;
d[1] = amount[1];
if (n >= 2) {
d[2] = amount[1] + amount[2];
}
for (int i = 3; i <= n; i++) {
d[i] = Math.max(d[i - 1], Math.max(d[i - 2] + amount[i], d[i - 3] + amount[i - 1] + amount[i]));
}
System.out.println(d[n]);
br.close();
}
}
난이도가 중하인 DP 문제는 알맞은 점화식을 찾는 것이 중요하다고 생각한다.
'CS > PS' 카테고리의 다른 글
최단 경로 알고리즘 정리 (0) | 2022.08.28 |
---|---|
Programmers: 큰 수 만들기 (0) | 2022.08.11 |
[백준 11721] 열 개씩 끊어 출력하기 Java11 (0) | 2021.01.08 |