백준 2156 포도주 시식 (Java)

1. 문제 링크

2156번: 포도주 시식

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. dp로 풀었다.

2. 2번째 잔까지는 3연속을 신경쓰지 않아도 되기에 더한 값을 넣는다.

3. 3번째 잔 부터는 연속 3개가 안되기 때문에 비교하여 더 큰 값을 저장했다.

    3-1. 지금잔을 선택하지 않는 경우

    3-2. 하나 앞의 잔을 선택하지 않고, 지금 잔을 선택하는 경우

    3-3. 두개 앞의 잔을 선택하지 않고, 하나 앞의 잔과 지금 잔을 선택하는 경우

 

4. 코드

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

public class Main {
	static int num[], dp[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		num = new int[N+1];
		dp = new int[N+1];
		for(int i=1;i<N+1;i++) {
			num[i] = Integer.parseInt(br.readLine());
		}
		
		dp[0] = 0;
		dp[1] = num[1];
		if(N>1) { //2번째 잔은 무조건 2개 합
			dp[2] = num[1] + num[2];
		}
		
		for(int i=3;i<N+1;i++) {
			//지금 잔 선택 X vs 하나 앞 잔 선택 X vs 두번 앞 잔 선택 X
			dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+num[i], dp[i-3]+num[i-1]+num[i]));
		}
		
		System.out.println(dp[N]);
	}
}