백준_포도주마시기_2156[Java]

문제

https://www.acmicpc.net/problem/2156

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

불러오는 중입니다...