[BAEKJOON] 2156번 : 포도주시식 (JAVA)

- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식

- 사용 언어 : JAVA

- 문제 요점

1. 3잔 연속으로 마시는 것 금지
   1. 현재 잔으로부터 이전 3번 째 잔까지만 확인
   2. 3번 째 잔부터 아래 3개의 항목 중 값이 큰 항목으로 적용
      1. 현재 잔 안마시기
      2. 2번째 전의 잔까지 마셨던 거 + 현재 잔 마시기
      3. 3번째 잔의 전까지 마셨던 거 + 이전 잔 마시기 + 현재 잔 마시기)
2. 포도주의 잔 갯수는 1이상이므로, d[2] 계산식을 조건에 두어 처리

 

소스 설명은 주석을 참고해주세요.

 

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N+1];
		int[] d = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		d[1] = arr[1];
		// 포도주의 잔 갯수가 1이 될 수도 있기에 에러를 방지 
		if(N>1) {
			d[2] = arr[1] + arr[2];
		}
		
		// 조건 : 연속 3잔만 마시면 되지 않음
		// 아래 3가지 경우 중, 큰 것 선택
		// (현재 잔 안마시기) or (2번째 전의 잔까지 마셨던 거 + 현재 잔 마시기) or (3번째 잔의 전까지 마셨던 거 + 이전 잔 마시기 + 현재 잔 마시기) 
		for(int i=3; i<=N; i++) {
			d[i] = Math.max(d[i-1],Math.max(d[i-2] + arr[i], d[i-3] + arr[i-1] + arr[i]));
		}
		
		System.out.println(d[N]);
	}
}

 

좋은 지적과 지식 공유는 언제나 환영합니다^^