[백준, JAVA] 2156번 : 포도주 시식

1. 문제

2. 아이디어

• 2579번 계단 오르기 문제와 상당히 유사하다.
  https://velog.io/@dev_su_noh/%EB%B0%B1%EC%A4%80-JAVA-2156%EB%B2%88-%ED%8F%AC%EB%8F%84%EC%A3%BC-%EC%8B%9C%EC%8B%9D

• 큰 차이점은, 계단은 1칸 혹은 2칸으로 제한되어 있었지만, 해당 문제는 그러한 조건이 없다.

• 바로 왼쪽(i-1)의 포도주를 마신 경우 / 마시지 않은 경우로 나누어 생각한다.
  마시지 않은 경우에는, i-2까지의 경우 중 최선을 선택해야 한다.

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
 
		int[] dp = new int[N + 1];
		int[] arr = new int[N + 1];
 
 
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
 
		// index = 0 은 시작점
		dp[1] = arr[1];
		
		if (N > 1) {
			dp[2] = arr[1] + arr[2];
		}

		for (int i = 3; i <= N; i++) {
			dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
 
		}
		System.out.println(dp[N]);
 
	}
 
}

4. 느낀점

• 계단 오르기 문제를 열심히 풀었더니 쉬웠다!

• DP 문제들은 index 및 dp/arr 배열 활용 로직을 고민하는 것이 중요하다.
  (역시 경우의 수를 몇가지 적어보는 것이 아주 좋다.)