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

·2021년 7월 1일
0

Algorithm

목록 보기
7/60

문제

BOJ 2156 : 포도주 시식 - https://www.acmicpc.net/problem/2156

풀이

와인 3잔을 연속해서 마실 수 없기 때문에 현재 위치에서 OOX, OXO, XOO의 경우 중 어떤 것이 가장 많이 먹을 수 있는 경우인지 판단해가면 된다. (맨 오른쪽이 현재 위치가 된다. 현재 위치를 기준으로 하나 전, 두개 전 경우를 보면 된다.)

예시를 보자면, 현재 인덱스 i가 2일때 다음과 같은 경우의 수가 만들어진다.

<OOX>

와인 순서0123456
선택 여부OOX

<OXO>

와인 순서0123456
선택 여부OXO

<XOO>

와인 순서0123456
선택 여부XOO

먼저 int[] dp 배열을 만든다.

  1. OOX : dp[i-1]
  2. OXO : dp[i-2] + wines[i]
  3. XOO : dp[i-3] + wines[i-1] + wines[i]

위 세 가지 경우 중 가장 max값을 dp[i]에 저장한다. 최종적으로 dp[n-1]에 저장되는 수가 마실 수 있는 와인의 최댓값이 된다.

dp[0]과 dp[1], dp[2]는 예외처리 해준다.

  • dp[0]은 wines[0] 자체가 최댓값이 된다.
  • dp[1]은 wines[0] + wines[1]가 최대값이 된다.
  • dp[2]는 Math.max(dp[1], wines[0]+wines[2], wines[1]+wines[2])를 구한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] wines = new int[n];
        for (int i = 0; i < n; i++) {
            wines[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[n];
        dp[0] = wines[0];

        for (int i = 1; i < n; i++) {
            if(i==1){
                dp[1] = wines[0] + wines[1];
                continue;
            }
            if(i==2){
                dp[2] = Math.max(dp[1], Math.max(wines[0]+wines[2], wines[1]+wines[2]));
                continue;
            }
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + wines[i], dp[i - 3] + wines[i-1] + wines[i]));
        }

        System.out.println(dp[n-1]);
    }
}


정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

  • DP는 할때마다 어떻게 풀어내야 할지 생각하는게 너무 어렵다.. 일단 시간초과가 예상되면 DP를 한번 생각할 것. DP는 memorization과 점화식이 key point! memorization을 어떻게 해서 중복 연산을 줄일 것인지를 잘 생각해보자.
  • n의 범위가 1부터이기 때문에 처음에 요렇게 0, 1, 2를 밖에다 해주어서 index에러가 났다. 범위 잘 보자!
int[] dp = new int[n];
dp[0] = wines[0];
dp[1] = wines[0] + wines[1];
dp[2] = Math.max(dp[1], Math.max(wines[0]+wines[2], wines[1]+wines[2]));
for (int i = 3; i < n; i++) {
      dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + wines[i], dp[i - 3] + wines[i-1] + wines[i]));
}

- dp문제는 풀때 너무 어려운데 풀고나면 코드가 너무 짧아서 현타(?)가 온다,,, 풀고나면 별거 아니니 쫄지 말기!


참고 사이트

https://zoonvivor.tistory.com/133
https://hees-dev.tistory.com/30

profile
당근먹고 자라나는 개발자

1개의 댓글

comment-user-thumbnail
2024년 5월 17일

와 이 문제 풀이 중에 가장 깔끔하고 직관적으로 잘 해주신 것 같아요 덕분에 잘 이해했습니다 감사합니다!

답글 달기