[백준] 2156번 포도주 시식 (DP_JAVA)

DP를 연습한다고 하는데,

난이도가 높아질수록 정말 어려움을 많이느꼈다.

 

원리를 제대로 파악하려고 노력하자!

 

---

문제

 

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

2156번: 포도주 시식

 

 

---

설계

 

알고리즘 설계 [접근 방법] : DP

전형적인 DP문제다.

와인을 연속적으로 3잔을 마실수 없기에, 현재 위치에서 고를 수 있는 선택지는 다음과 같다.

`xoo`, `oxo`, `oox`의 경우 중 어떤 것이 가장 많이 먹을 수 있는 방법인지 선택하면 된다.

 

dp배열을 2차원 배열로 생성한 후,

현재 값을 0번째 행에 저장하고, 현재 값에 마실 수 있는 최대의 와인 양을 1번 행에 저장한다.

 

예시를 들어 와인잔이 3개가 있다고 생각해보자.

첫 번째, `xoo`같은 경우는 현재 잔과 그 전의 잔을 마시는 경우다.

코드로 나타낸다면, dp[1][i-3] + dp[0][i-1] + dp[0][i]가 된다.

와인 순서	0	1	2
선택 여부	X	O	O

 

두 번째,  `oxo`의 경우는 전전의 잔을 마시고, 현재 잔을 마시는 경우다.

이 경우에는 최대 값은  dp[1][i-2] + dp[0][i]이 되는 것이다.

와인 순서	0	1	2
선택 여부	O	X	O

 

세 번째,  ` oox `의 경우는 전전의 잔과 전의 잔을 마시고,  현재 잔을 마시지 않는 경우다.

이 경우는 dp[1][i-1]이 되는 것이다.

와인 순서	0	1	2
선택 여부	O	O	X

 

 

풀이 과정

1.

포도주 개수인 n을 입력받는다.

 

2.

2차원 배열 dp를 생성하고, 0번 행에 와인의 양을 입력받는다.

최대 i-3까지 탐색해야 하므로 2차원 배열의 크기를 dp[2][n+3]으로 생성한다.

 

3.

`xoo`, `oxo`, `oox`의 경우 중 어떤 것이 가장 많이 먹을 수 있는 방법인지 선택한다.

dp[1][i-3] + dp[0][i-1] + dp[0][i], dp[1][i-2] + dp[0][i],  dp[1][i-1]를 비교해 가장 큰 값을 dp[1][i]에 저장한다.

 

4.

dp[1]의 행을 반복문을 돌면서 최대값을 찾는다.

 

5.

최대 값을 출력한다.

 

 

---

코드

 

import java.util.*;

public class Test_2156_포도주시식 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//포도주 개수 입력받기
		int n = sc.nextInt();
		
		//dp배열 생성하기
		int[][] dp = new int[2][n+3];
		for(int i=3; i<n+3; i++) {
			dp[0][i] = sc.nextInt();
		}
		
		//현재 잔으로 오기까지 최대값 
		for(int i=3; i<n+3; i++) {
			int one = dp[1][i-3] + dp[0][i-1] + dp[0][i];	//xoo
			int two = dp[1][i-2] + dp[0][i];		//oxo
			int three = dp[1][i-1];				//oox
			
			dp[1][i] = Math.max(one, Math.max(two, three));
		}
		
		//최대값 구하기
		long max = 0;
		for(int i=0; i<n+3; i++) {
			if(max<dp[1][i]) max = dp[1][i];
		}
		
		//출력
		System.out.println(max);
	}
}

 

 

(❁´◡`❁)

끝!