[오답노트] BOJ 2156: 포도주시식 - JAVA

---

출처 : https://www.acmicpc.net/problem/2156
난이도 : 실버 1
풀이날짜 : 2022-12-31

---

---

풀이

아이디어

이 문제는 중요한 것은 '연속으로 놓여 있는 3잔을 모두 마실 수는 없다.' 라는 점이다.
이 부분을 해결하기 위해서는 DP로 경우를 나눠야 한다.

1. 이 잔이 선택되지 않았을 때
2. 이 잔이 선택되었으나 전 잔이 선택되지 않았을 때
3. 이 잔이 선택되었으나 전 잔이 선택되었을 때

풀이는 다음과 같다.
arr 배열에 각 순서의 술잔의 양을 저장한다.
dp int 2차원 배열을 만들어 dp[i][0]은 선택되지 않은 경우, dp[i][1]은 선택되었으나 전 잔이 선택되지 않은 경우, dp[i][2]는 전 잔과 이 잔이 선택된 경우로 하면 된다.

추가적으로 dp[i][3]으로 dp[i][0], dp[i][1], dp[i][2] 중의 최댓값을 저장하면 최댓값 연산을 줄일 수 있다.

1. 이 잔이 선택되지 않았으니 이 경우의 최댓값은 이전에 dp에서의 최댓값이 된다.
dp[i][0] = Math.max(dp[i - 1][0], dp[i -1][1], dp[i - 1][2])이 된다.

2. 이 잔이 선택되었으나 전 잔이 선택되지 않은 경우는 dp[i-1][0](전 잔이 선택되지 않은 경우) + arr[i]가 된다.

3. 이 잔이 선택되고 전 잔도 선택된 경우는 dp[i-1][1] + arr[i]가 된다.

---

코드

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

public class No2156 {
	
	static int n;
	static int[] arr;
	static int[][] dp;
	
	public static void main(String[] args) throws IOException {
		input();
		pro();
	}

	private static void pro() {
		int max = 0;
		for(int i=0; i<n;i++) {
			max = Math.max(max,dp[i][3]);
		}
		System.out.println(max);
	}	

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		dp = new int[n][4];
		
		arr[0] = Integer.parseInt(br.readLine());
		dp[0][1] = arr[0];
		dp[0][3] = arr[0];
		
		for(int i=1; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			int max = dp[i-1][3];
			dp[i][0] = max;
			dp[i][1] = dp[i-1][0] + arr[i];
			max = Math.max(dp[i][1], max);
			dp[i][2] = dp[i-1][1] + arr[i];
			max = Math.max(dp[i][2], max);
			dp[i][3] = max;
		}
		br.close();
	}
}

---

결과

---

느낀점

처음 풀었을 때는 감을 잡지 못하여 오답노트에 적었지만 빠르게 풀이가 떠올랐다. 다음에는 이런 유형의 문제가 나올시 쉽게 대처가 가능할 것 같다. 유사한 문제로 더 난이도가 높은 문제들을 풀어봐야 할 것 같다.