0%

[백준/2156] 포도주 시식

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2156

Review

  • 경우는 총 세 가지

    1. 현재 포도주는 마시지 않을 경우
    2. 현재 포도주는 마시고 이전 포도주는 마시지 않은 경우
    3. 현재 포도주와 이전의 포도주를 마신 경우

  • 각각의 경우를 점화식으로 나타내면 다음과 같다.

    1. dp[i - 1]
    2. wine[i] + dp[i - 2]
    3. wine[i] + wine[i - 1] + dp[i - 3]

  • 여기서 dp[]는 포도주를 마신 최대값이 되고, wine[]은 포도주의 양이다.

Code (JAVA)

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
36
37
38
39
40
41
42
43
import java.util.*;

public class Main {
  
  public static int Max(int a, int b, int c) {
    if(b > c) {
      return a > b ? a : b;
    } else {
      if(a > c) {
        return a;
      } else {
        return c;
      }
    }
  }
  
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    
    int[] wine = new int[10001];
    int[] dp = new int[10001];
    
    // 배열 초기화
    for(int i = 1; i <= N; i++) {
      wine[i] = sc.nextInt();
    }

    dp[0] = 0;
    dp[1] = wine[1];
    dp[2] = dp[1] + wine[2];
    
    // 값 비교
    for(int i = 3; i <= N; i++) {
      dp[i] = Max(dp[i-1], wine[i] + dp[i-2], wine[i] + wine[i-1] + dp[i-3]);
    }
    
    System.out.println(dp[N]);
    sc.close();
    
  }
  
}