백준
DP #2156: 포도주 시식 [JAVA]
chaechaepower
2023. 6. 6. 00:38
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
문제 접근
https://chaechaepower.tistory.com/17
> 과거의 내가 아주 잘 정리해둠.
n=5에서 5번째 잔을 포함시켰을 때 마실 수 있는 최대의 양과
5번째 잔을 포함시키지 않고 이전에 n=4에서 마실 수 있는 최대의 양
을 비교해야한다.
코드
top down - 재귀
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Integer[] dp;
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
dp = new Integer[N + 1];
arr = new int[N + 1];
for (int i = 0; i < N; i++) {
arr[i + 1] = Integer.parseInt(bf.readLine());
}
dp[0] = 0;
dp[1] = arr[1];
if (N >= 2) {
dp[2] = arr[1] + arr[2];
}
System.out.println(recur(N));
bf.close();
}
static int recur(int n) {
if (dp[n] == null) {
dp[n] = Math.max(recur(n - 1), Math.max(arr[n] + arr[n - 1] + recur(n - 3), arr[n] + recur(n - 2)));
}
return dp[n];
}
}
bottom up - 반복문
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Integer[] dp;
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
dp = new Integer[N + 1];
arr = new int[N + 1];
for (int i = 0; i < N; i++) {
arr[i + 1] = Integer.parseInt(bf.readLine());
}
dp[0] = 0;
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(arr[i] + arr[i - 1] + dp[i - 3], arr[i] + dp[i - 2]));
}
System.out.println(dp[N]);
bf.close();
}
}