백준 알고리즘 2156번: 포도주 시식

문제 정보

---

 

2156번: 포도주 시식

 

 

핵심

---

 

백준 알고리즘: 2579번 계단 오르기

동적 계획법(DP) 알고리즘을 사용하여 문제를 풀이한다

위 링크한 문제인 계단 오르기 문제와 언뜻 보면 비슷해 보이지만, 계단 오르기에 경우에는 한번에 한 계단 혹은 두 계단을 반드시 올라야 하지만 위 문제의 경우에는 연속으로 놓여 있는 세잔의 포도주만 마실 수 없을 뿐 여러 잔을 띄어서 마실 수 있다

이 부분이 제일 헷갈렸던 부분인데 예를 들어 다음과 같은 입력이 있을 때

10
0
0
10
0
5
10
0
0
1
10

이어진 0만큼의 포도주 2잔을 선택하지 않는 쪽이 더 많은 포도주를 마실 수 있는 효율적인 방법이기 때문에

위에 말했던 부분을 생각하지 않는다면 최대의 양이 나오지 않기 때문에 꼭 생각해 주어야 한다

 

처음에는 아래와 같은 코드를 작성하여서

for (int i = 3; i <= N; i++) {
	dp[i] = Math.max(dp[i - 2], dp[i - 3] + table[i - 1]) + table[i];
}

현재 위치를 반드시 선택하는 전제 조건 하에, 한칸 전의 포도주 혹은 두칸 전의 포도주의 선택하기 때문에 위 조건을 만족하지 못했지만

 

for (int i = 3; i <= N; i++) {
	dp[i] = Math.max(dp[i - 2], dp[i - 3] + table[i - 1]) + table[i];
	dp[i] = Math.max(dp[i], dp[i - 1]);
}

다음과 같이 3가지 경우를 계산하여 이 중 최대값을 현재 위치에서의 최대값으로 설정하는 과정을 통하여 만족시킬 수 있다

1. 현재 위치를 선택, 직전 위치를 선택

2. 현재 위치를 선택, 2칸 전 위치를 선택(직전 위치 선택 X)

3. 현재 위치를 선택하지 않음

 

풀이

---

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

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[] table = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      table[i] = Integer.parseInt(br.readLine());
    }
    int[] dp = new int[N + 1];
    dp[0] = 0;
    dp[1] = table[1];

    if (N == 1) {
      System.out.println(dp[1]);
      return;
    }

    dp[2] = table[1] + table[2];
    if (N == 2) {
      System.out.println(dp[2]);
      return;
    }

    for (int i = 3; i <= N; i++) {
      dp[i] = Math.max(dp[i - 2], dp[i - 3] + table[i - 1]) + table[i];
      dp[i] = Math.max(dp[i], dp[i - 1]);
    }

    System.out.println(Arrays.stream(dp).max().getAsInt());
  }
}

 

Source Code on GitHub

---