Hard_2156_포도주 시식

문제 링크(Click) : https://www.acmicpc.net/problem/2156

1. 문제 접근

---

1) 문제가 반복되는지? 즉, 재귀/DP 문제인지 파악합니다.

  개인적으로 '알고리즘 기초'에 있는 DP 문제들 중에서 2번째로 어려웠던 문제입니다. 먼저, 문제에서 주어진 예시를 통해서 문제의 요구사항을 파악해 보겠습니다. 

 " 효주가 가장 많은 포도주를 마실 수 있도록 하는 프로그램을 작성해라 "

 " 단, 포도주 잔을 선택하면 그 잔에 들어있는 포두주를 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. "

 " 단, 연속으로 놓여 있는 3잔을 마실 수는 없다. "

  저는 이러한 DP 문제에 접근할 때, 끝에서부터 생각을 하는 습관이 도움이 된다고 생각합니다. 따라서 아래의 그림으로 표현할 수 있게 됩니다. (빨간색 부분은 연속으로 마신 횟수를 의미합니다.)

  이를 통해, 연속으로 마신 횟수에 따라 다음 번에 마실수 있는지의 여부가 결정됨을 확인할 수 있습니다. (연속으로 마신 마신 횟수가 2인 경우, 다음에는 무조건 마시지 말아야한다.)

  또한, 위 그림에서 노란색으로 표시된 것 처럼 '1차원 d 배열'을 이용할 경우, 다음의 값(안마실 때)이 기존의 값(마실 때)을 덮어 씌워지는 것을 방지하기 위해 '2차원 d 배열'을 활용하여 이를 해결할 수 있습니다.

 '2차원 d 배열'을 이용한다는 점을 이해하는데 어려우시다면 블로그에 포스팅된 Normal_10844_쉬운 계단 수(click) 문제에 제시된 것을 보면 도움이 될 것입니다. (그래도 이해가 가지 않는다면, 댓글이나 질문 게시판을 이용해주시면 감사하겠습니다!)

 2) 종료 조건을 파악합니다.

  위 그림은 개수가 4인 포도주 잔에서 마실 수 있는 최대 양을 구하는 모습입니다. 뒤에서부터(index 4 -> 1) 차례대로 경우를 따져보다가 마지막 index 1의 값을 채우고 나면, 그 경우가(노란색 부분) 개수가 4인 포도주 잔에서 마실 수 있는 최대 양임을 알 수 있습니다. 따라서 index가 0일 경우, 양이 0인 포도주를 마시는 경우임과 동시에 재귀함수의 종료 조건이라는 것을 알 수 있습니다. 

 if(n == 0) return 0;

 3) 반복 패턴을 코드화 합니다.

  1) 에서 이야기 했던 것처럼, 연속으로 마신 횟수에 따라 다음 번에 마실수 있는지의 여부가 결정됨을 확인할 수 있습니다. (연속으로 마신 마신 횟수가 2인 경우, 다음에는 무조건 마시지 말아야한다.) 따라서 연속으로 두 번 마신 경우와 그렇지 않은 경우로 분류해 계산을 해줘야합니다. 

  먼저, 연속으로 두 번 마신 경우, 다음에는 마실 수 없으므로 다음과 같이 조건문을 사용하여 처리합니다.

if(count == 2)

d[n][count] = dp(n-1) + 0;

 

  다음으로 연속으로 두 번 마시지 않은 경우, 다음 것을 마실 수도 있고 마시지 않을 수도 있습니다. 이 중 큰 값을 갖는 것이 문제에서 말한 요구사항을 만족하는 것으므로 다음과 같이 조건문을 사용하여 처리합니다. 

else

d[n][count] = Math.max(dp(n-1, count + 1) + wine[n], dp(n-1, 0));

  약간의 설명을 덧붙이자면, Math.max 내의 첫 번째 파라미터는 현재 포도주를 마신 경우이고(따라서, +wine[n]을 해준다.), 두 번째 파라미터는 현재 포도주를 마시지 않은 경우 입니다.(따라서, 연속으로 마신 횟수가 0이고, +wine[n]을 해주지 않는다.)

2. 코드 종합

---

 위에서 정리된 코드들을 아래의 순서로 정리하면 완성할 수 있습니다.

 1) 종료 조건

 2) Memoization

 3) 반복 패턴

 4) return d[n][count];

import java.util.Scanner;

public class p2156 {

static long[][] d;

static long[] wine;

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

wine = new long[n+1];

d = new long[n+1][3];

for(int i = 1; i <= n; i++)

wine[i] = scan.nextLong();

System.out.println(dp(n, 0));

}

public static long dp(int n, int count) {

if(n <= 0)

return 0;

if(d[n][count] > 0)

return d[n][count];

if(count == 2) {

d[n][count] = dp(n-1, 0);

} else {

d[n][count] = Math.max(dp(n-1, count+1)+wine[n], dp(n-1, 0));

}

return d[n][count];

}

}