알고리즘(Algorithm)의 종류, 분류/동적프로그래밍(Dynamic Programming)

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

Miiko 2021. 9. 15. 00:17

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

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

 

 

 

 

 

 

 

 

| 문제 해결방법

 

 이 문제는 백준의 DP문제인 2579번_계단 오르기 문제와 거의 동일하다.

 

고려해야할 조건은 3번 연속으로 포도주를 마시면 안되는 것으로 계단 오르기 문제와 동일하고,

 

이 문제에서 추가해준 조건은 

 

해당 위치의 포도주를 마신 경우마시지 않은 경우의 포도주량을 비교해 더 큰 값을 메모제이션 해주는 것이다. 

 

계단오르기는 수의 크기가 오름차순으로 이루어져 있었기 때문에 이를 고려해줄 필요가 없었지만,

 

포도주는 수의 크기가 정렬되어 있지 않기 때문에 추가해줘야 한다.

 

(처음에는 계단오르기와 동일하게 풀었다가 두 번이나 틀리고서야 이 조건을 추가해줘야 한다는 것을 알게 되었다.)

 

 

[JAVA] 해설 코드

 

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

public class Main {

	static int N;
	static long[] arr, dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		
		arr = new long[N+1];
		dp = new long[N+1];
		for(int i=1;i<=N;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		dp[1] = arr[1];
		if(N>=2) {
			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(Arrays.stream(dp).max().getAsLong());
	}

}