[JAVA] 백준 2156. 포도주 시식

이 글은 읽는데 약 4분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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

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

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

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

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

풀이

문제를 보다 보면 이전에 풀었던 2579. 계단 오르기 문제와 비슷한 것 같다는 느낌을 받을 수 있다. 실제로도 조건 등이 유사하다. 다만 차이점이라면 계단 오르기 문제는 마지막 계단을 무조건 밟아야 하지만, 이 문제는 예시만 보아도 마지막 포도주를 무조건 마실 필요는 없다는 것을 알 수 있다.

계단 문제와 겹치는 부분이 있으니 아직 계단 문제를 풀어보지 않았다면 먼저 보고 오는 것도 이해에 좋을 것 같다.

그러므로 계단 문제와는 다르게 이번에는 총 세 가지 경우에 대해서 검사를 해야한다.

  • 현재 포도주를 마시지 않는다
  • i-2번 포도주와 현재 포도주를 마신다
  • i-3번 포도주와 i-1번 포도주와 현재 포도주를 마신다.

dp 배열을 만들어서 풀이할 것인데, 이 배열이 의미하는 바는 dp[i]는 i번째 까지 가능한 가장 큰 포도주 양을 값으로 가진다.

계단 문제와 다른 점이라면 현재 포도주를 마시지 않고 이전 포도주 까지의 최대 양을 그대로 따르는 경우도 고려해야 한다는 것이다.

그러므로 현재 포도주가 i번, 각 포도주의 양을 저장하는 배열을 cup이라고 하면

  • dp[i-1]
  • dp[i-2] + cup[i]
  • dp[i-3]+cup[i-1]+cup[i]

위 세 값 중 최대값을 찾아 dp[i]에 저장해 주면 되는 것이다. 그리고 마지막으로 dp[N] 값을 출력해주면 끝이다.

코드

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    sb = new StringBuilder();

    int N = Integer.parseInt(br.readLine());
    int[] cup = new int[N+1];
    int[] dp = new int[N+1];

    for(int i=1; i<=N; i++){
        cup[i] = Integer.parseInt(br.readLine());
    }

    // dp[0] = 0;
    dp[1] = cup[1];
    if(N >= 2){
        dp[2] = cup[1] + cup[2];
    }

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

    sb.append(dp[N]);
    System.out.println(sb.toString());
    br.close();
}

댓글