https://www.acmicpc.net/problem/2156
| 문제 해결방법
이 문제는 백준의 DP문제인 2579번_계단 오르기 문제와 거의 동일하다.
고려해야할 조건은 3번 연속으로 포도주를 마시면 안되는 것으로 계단 오르기 문제와 동일하고,
이 문제에서 추가해준 조건은
해당 위치의 포도주를 마신 경우와 마시지 않은 경우의 포도주량을 비교해 더 큰 값을 메모제이션 해주는 것이다.
계단오르기는 수의 크기가 오름차순으로 이루어져 있었기 때문에 이를 고려해줄 필요가 없었지만,
포도주는 수의 크기가 정렬되어 있지 않기 때문에 추가해줘야 한다.
(처음에는 계단오르기와 동일하게 풀었다가 두 번이나 틀리고서야 이 조건을 추가해줘야 한다는 것을 알게 되었다.)
[JAVA] 해설 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N;
static long[] arr, dp;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new long[N+1];
dp = new long[N+1];
for(int i=1;i<=N;i++) {
arr[i] = Integer.parseInt(br.readLine());
}
dp[1] = arr[1];
if(N>=2) {
dp[2] = arr[1]+arr[2];
}
for(int i=3;i<=N;i++) {
// 해당 위치의 포도주를 안마시는 경우, 마시는 경우를 비교
dp[i] = Math.max(dp[i-1],Math.max(dp[i-2] + arr[i], dp[i-3]+arr[i-1] + arr[i]));
}
System.out.println(Arrays.stream(dp).max().getAsLong());
}
}
'알고리즘(Algorithm)의 종류, 분류 > 동적프로그래밍(Dynamic Programming)' 카테고리의 다른 글
[JAVA]백준 11727번: 2×n 타일링 2 (0) | 2021.09.16 |
---|---|
[JAVA]백준 10844번: 쉬운 계단 수 (0) | 2021.09.16 |
[JAVA]백준 1520번: 내리막 길 (0) | 2021.09.13 |
[JAVA]백준 11722번: 가장 긴 감소하는 부분 수열 (0) | 2021.09.12 |
[JAVA]백준 11053번: 가장 긴 증가하는 부분 수열 (0) | 2021.09.12 |