문제 :
https://www.acmicpc.net/problem/2156
접근 :
- 마지막 포도주를 마시는 경우와 마시지 않는 경우를 나눈다.
- 만약 마지막 포도주를 마시지 않는 경우, 1) 이전까지(n-1)의 최대값이 정답이다.
- 마지막 포도주를 마시는 경우, 2) 3번째 전(n-3) 최대값에 전 포도주 잔(n-1)과 이번 포도주 잔(n)을 마실 수 있다.
- 또한, 3) 2번째 전(n-2) 최대값에 이번 포도주 잔(n)을 마실 수 있다.
- 1) 2) 3) 3가지 경우 중 최대값을 정답으로 출력한다.
코드 구현 :
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[] dp = new int[n+1];
dp[0] = 0;
dp[1] = Integer.parseInt(br.readLine());
if(n == 1) {
System.out.println(dp[1]);
return;
}
int before = Integer.parseInt(br.readLine());
dp[2] = dp[1] + before;
int now;
for(int i = 3 ; i <= n ; i++){
now = Integer.parseInt(br.readLine());
dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + before + now, dp[i-2] + now));
before = now;
}
System.out.println(dp[n]);
}
}
'JAVA > Coding Test' 카테고리의 다른 글
[JAVA] 백준 1520 내리막길_DP (0) | 2024.06.25 |
---|---|
[JAVA] 백준 2193 이친수_DP (0) | 2024.06.24 |
[JAVA] 백준 2011 암호코드 _DP (0) | 2024.06.21 |
[JAVA] 백준 11052 카드 구매하기_DP (0) | 2024.06.20 |
[JAVA] 백준 3055 탈출_BFS (0) | 2024.06.18 |