백준_포도주마시기_2156[Java]
2019. 4. 24. 12:13ㆍ알고리즘문제/백준
문제
https://www.acmicpc.net/problem/2156
풀이
오랜만에 DP문제를 풀어보는 것 같다.
포도주를 최대 2번 연속 마실 수 있으므로
0번 연속으로 마시는 경우
1번 연속으로 마시는 경우
2번 연속으로 마시는 경우로 나눌 수 있겠다.
wine[] : 각 위치별 포도주의 양
DP[] : 포도주 n개가 주어졌을 때, 가장 많이 마실 수 있는 양
을 이용해서 아래와 같은 점화식을 만들 수 있다.
0번 연속으로 마시는 경우 : DP[n] = DP[n-1]
1번 연속으로 마시는 경우 : DP[n] = wine[n]+ DP[n-2]
2번 연속으로 마시는 경우 : DP[n] = wine[n]+ wine[n-1] + DP[n-3]
코드
import java.util.Scanner;
public class Main {
static int n;
static int[] wine;
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
wine = new int[n+1];
dp = new int[n+1];
for(int i = 1; i <= n; i++) {
wine[i] = sc.nextInt();
}
dp[1] = wine[1];
if(n > 1) { // n == 1인 경우 예외 발생하므로
dp[2] = wine[1]+ wine[2];
}
for(int i = 3; i <= n; i++) {
dp[i] = Math.max(dp[i-1], Math.max(wine[i] + dp[i-2], wine[i] + wine[i-1] + dp[i-3]));
}
System.out.println(dp[n]);
sc.close();
}
}
참고
https://limkydev.tistory.com/112
'알고리즘문제 > 백준' 카테고리의 다른 글
백준_파일 합치기_11066[Java] (0) | 2019.04.24 |
---|---|
백준_로봇 조종하기_2169[Java] (0) | 2019.04.24 |
백준_말이 되고픈 원숭이_1600[Java] (0) | 2019.04.22 |
백준_통나무 옮기기_1938[Java] (0) | 2019.04.19 |
백준_안전영역_2468[Java] (0) | 2019.04.19 |