[백준 / BOJ] 2156번 : 포도주 시식 - JAVA

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

다이나믹 프로그래밍

포도주를 마시는 효주에게는 세 가지 상태가 있고, 각 상태에서 효주가 고를 수 있는 선택지도 정해져 있다.

 

0. 이전 잔을 안 마신 상태 : 현재 잔을 마시면 1번 상태로 가고, 마시지 않으면 0번 상태에 머무른다.
1. 직전에 한 잔 마신 상태 : 현재 잔을 마시면 2번 상태로 가고, 마시지 않으면 0번 상태로 간다.
2. 직전에 두 잔 마신 상태 : 현재 잔을 마실 수 없으므로 0번 상태로 간다.

 

따라서 포도주마다 세 가지 상태를 바탕으로 N * 3 배열을 만들었다.

 

0. wine[i][0] 은 이전에 얼마나 마셨건 이번 잔은 마시지 않는 걸 의미한다. 따라서 wine[i - 1][0], wine[i - 1][1], wine[i - 1][2] 중 가장 큰 값을 저장한다.
1. wine[i][1] 은 이전에 마시지 않았던 상태에서 이번 잔을 마시는 걸 의미한다. 따라서 wine[i - 1][0] + 이번 잔을 저장한다.
2. wine[i][2] 는 이전에 한 잔 마셨던 상태에서 이번 잔을 마시는 걸 의미한다. 따라서 wine[i - 1][2] + 이번 잔을 저장한다.

N번째 포도주 시식 여부를 결정한 뒤, 가장 큰 값을 찾아서 출력한다.

 

놓치기 쉬운 반례

처음에는 wine[i][0]에 wine[i - 1][1]과 wine[i - 1][2] 중 큰 값을 넣어줬는데, 다음과 같은 반례 때문에 틀리게 된다.

6
100
100
1
1
100
100

정답 : 400

최대값을 위해서는 포도주 잔을 연속으로 건너뛸 수도 있다.

 

전체 코드

// 시간 : 100ms
// 메모리 : 13068KB
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[][] wine = new int[N+1][3];
		
		for (int i = 1; i <= N; i++) {
			int n = Integer.parseInt(br.readLine());
			wine[i][0] = Math.max(Math.max(wine[i - 1][1], wine[i - 1][2]), wine[i - 1][0]);
			wine[i][1] = wine[i - 1][0] + n;
			wine[i][2] = wine[i - 1][1] + n;
		}
		
		System.out.println(Math.max(wine[N][0], Math.max(wine[N][1], wine[N][2])));
	}

}