백준 2156 다이나믹프로그래밍

백준 2156

두가지 규칙중 첫번째는 문제를 푸는데 아무 상관없는 규칙입니다.

연속으로 3잔을 연속 마실 수 없는 점만 문제에 영향을 줍니다.

 

n번째 잔을 마실 차례라고 했을때 경우의 수는 세가지입니다.

1. n번째 잔을 안마신다
2. n번째 잔을 1연속으로 마신다

3. n번째 잔을 2연속으로 마신다

 

이 세가지 경우중 가장 큰걸 고르면 됩니다.

 

이걸 코드로 나타내면 아래와 같습니다.

public class B2156 {
	private static int N, wine[] , dp[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		wine = new int[N+1];
		dp  = new int[N+1];
		for(int i = 1; i<=N; i++) {
			wine[i] = Integer.parseInt(br.readLine());
		}
		
		dp[1] = wine[1];
		if(N > 1) {
			dp[2] = dp[1] + wine[2];
		}
		
		for(int i = 3; i<=N; i++) {
			dp[i] = Integer.max(dp[i-1], Integer.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]));
			
		}
		System.out.println(dp[N]);
	}
}