/ BOJ

BOJ_2156_포도주시식_JAVA

문제 : 포도주시식

링크 : BOJ_2156_포도주시식

접근 방식

DP 문제이다. 이 문제는 10일자 포스팅 계단오르기와 많은 부분이 유사한 문제이다.

연속된 3개의 포도주를 마실 수 없다는 점에서 계단오르기의 점화식을 일단은 사용할 수 있어보인다. 하지만, 함정이 있다. 계단오르기 문제에서는 마지막 발판을 무조건 밟아야 한다는 조건이 있었지만, 이 문제에는 그러한 조건이 없다. 따라서 자기자신을 선택하지 않는 경우의 수도 생각해야한다.

N번째 포도주를 먹는다고 할 때 가능한 경우의 수는 다음과 같다.

  1. N, N-1 번째 포도주를 먹는다.
  2. N, N-2 번째 포도주를 먹는다. 여기에 추가로 N번째 포도주를 먹지 않는 경우도 있다.
  3. N-1, N-2번째 포도주를 먹는다.

N-1번째 포도주와 dp의 N-3번에 누적된 값과 N번째 포도주와 dp의 N-2번에 누적된 값 중 최댓값을 골라 N번 째 dp 배열에 값을 넣을 수 있다.

현재 포도주를 먹지 않는 경우의 수도 있는데 이 부분은 내 바로 이전 값과 최댓값비교로 얻을 수 있다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_2156_포도주시식 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		int[] arr = new int[N+1];
		for(int i=1;i<=N;i++) {
			arr[i] = Integer.parseInt(in.readLine());
		}
		int[] dp = new int[N+1];

		dp[1] = arr[1];
		if(N >= 2) {
			dp[2] = arr[2] + arr[1];
		}
		for(int i=3;i<=N;i++) {

			dp[i] = Math.max(dp[i-2], dp[i-3] + arr[i-1]) + arr[i];
			dp[i] = Math.max(dp[i-1], dp[i]);
		}

		System.out.println(dp[N]);
	}

}