프로그래밍/Algorithm

[백준 알고리즘] 2156 - 포도주 시식

Jay Tech 2018. 11. 19. 19:18
반응형

백준 알고리즘 2156번 Dynamic Programming 문제를 풀어보았다.


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

  1. 포도주 잔을 선택하면 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 포도주 잔에 들어있는 포도주의 양이 주어졌을 , 효주를 도와 가장 많은 양의 포도주를 마실 있도록 하는 프로그램을 작성하시오

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 , 번째, 번째, 번째, 다섯 번째 포도주 잔을 선택하면 포도주 양이 33으로 최대로 마실 있다.


마지막 잔을 마셨을 때의 경우를 생각해보면 전전잔까지의 최대합 + 마지막잔 또는 전전전잔까지의 최대합 + 전잔 + 마지막잔 을 비교해서 최댓값을 구하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int glass = sc.nextInt();
        
        int[] w = new int[glass+1];
        int[] dp = new int[glass+1];
 
 
        for(int i = 1; i < glass + 1; i++) {
            w[i] = sc.nextInt();
        }
 
        if(glass == 1) {
            System.out.println(w[1]);
            return;
        }
 
        dp[1= w[1];
        dp[2= w[1+ w[2];
 
        for(int i = 3; i < glass + 1; i++) {
            dp[i] = max(dp[i-2+ w[i], dp[i-3+ w[i-1+ w[i]);
            dp[i] = max(dp[i], dp[i-1]);
        }
        
        System.out.println(dp[glass]);
    }
 
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
}
cs


두 잔을 연속으로 마시지 않는 경우가 있기 때문에 line 26에서 이전 dp 값과 비교를 해준다.


그리고 입력잔수가 1일때를 고려하지 않아서 런타임 에러가 터졌다. line 16에 1인경우를 넣어주었다. 

반응형