BOJ2156_포도주 시식

개요

2579번 문제(계단오르기)와 비슷한 방식의 연속합을 구해보자

문제 접근

포도주 잔의 개수 : $1\leq n \leq10,000$
시간 제한은 2초다

문제에서 제시하는 조건(연속하는 3잔은 마실 수 없다)에 집중하면 될거 같다 문제를 보자마자 계단 오르기 문제와 제한 조건이 흡사하여 문제 또한 비슷하다 생각했고 접근했다

그러나, 분명 계단오르기와 다른점은 계단오르기는 끝이 정해져 있었고, 이번 문제는 끝이 정해져 있지 않다

한번 이렇게 생각을 해보았다
계단오르기 점화식을 그대로 사용하였다
[보러가기]

문제의 예제 입력값을 입력한 결과이다
$N$번째 값이 더 작은 것을 확인할 수 있다

앞서 조건을 만족하며 구한 연속값은 최고로 커야하는데 만약 $N$번째에 있는 포도주를 먹으면 안되는 상황(작은 상황)이면? 연속된 합의 최댓값을 구할 수 없게 된다

그러므로 $dp[n]=Math.max(dp[i],dp[i-1])$로 표현할 수 있을거 같다

이를 구현한 코드 되시겠다.

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[10001];
		int[] dp = new int[10001];
		
		for(int i = 1; i <= n; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
		dp[1] = arr[1];
		dp[2] = arr[1] + arr[2];
		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], dp[i-1]);
		}
		bw.write(dp[n] + "");
		bw.close();
	}

}