BaekJoon : 2156번(포도주 시식)
Java : BaekJoon Dynamic Programming
BaekJoon Dynamic Programming(동적 프로그래밍) 저의 문제풀이 입니다.
혹시 더 좋은 방법 알려주신다면 정말 감사하겠습니다!
2156
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
입력
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
6 // 포도주 잔의 개수 n이 입력
6 // 여기부터 n개 만큼
10
13
9
8
1 // 포도주 잔에 들어있는 양을 입력합니다.
출력
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
33 // 최대로 마실 수 있는 포도주의 양을 출력합니다.
하나씩 나열해서 차근차근 찾는 방법
2579번(계단 오르기)과 비슷한 문제입니다. 하지만 다른 점은 고정 조건이 없다는 것입니다(예를 들어, 마지막 포도주 잔은 꼭 포함되어야 하는 경우 같은 것을 말합니다.) 이 점 때문에 조건찾기가 좀 까다로운 편입니다.
일단 포도주 잔의 순서 -> (최대 포도주가 되기위한 포도주잔의 번호),...으로 차근차근 표현해보겠습니다.
1 -> 1
2 -> (2,1) (1과 2도 있는데 1과 2는 (2,1)보다 항상 작습니다.)
3 -> (3,2) (3,1) (2,1) (3이 2보다 작을 경우 (2,1)이 더 클수도 있습니다.)
4 -> (4,3,1) (4,2,1) (3,2) (고정된 숫자가 없다 보니 경우의 수를 뽑아내는 데 좀 더 어려움이 있습니다.)
5 -> (5,4,2,1) (5,3,2) (4,3,1) (5,3,1) (뭔가 패턴이 보이기 시작합니다.)
본격적으로 패턴이 나오기 시작하는 4번부터 보면, (4,3,1) (4,2,1)의 (3,1) (2,1)은 3번의 경우 중 연속되지 않는 경우 2개에 +4를 한 것이고 (3,2)는 3의 경우중 제일 큰 두 숫자가 연속됐을 경우 입니다. 하지만 점화식으로 표현하기에는 아직 애매해 보이니 패스하고 5번을 봅니다.
5번의 (5,4,2,1) (5,3,2)을 보면 4번과 비슷하게 제일 큰 두 숫자가 연속됐을 경우를 제외한 나머지에 +5를 해줍니다. 역시 제일 큰 두 숫자가 연속됐을 경우는 그대로 올라오는 것을 볼 수 있습니다.
이 경우를 봤을 때, 5번과 4번을 비교해서 어떤 점화식을 도출하기에는 조금.. 애매해 보입니다.
그럼 일단 첫 번째로 5번과 3번을 한번 비교해 봅니다. 5번의 (5,3,2) (5,3,1) 과 3번(n-2)의 (3,2) (3,1)이 연관성을 보입니다..!! 그럼 혹시 3번의 (2,1)과도 연관성이 있을까요? 5번의 (5,4,2,1) 때문에 (5,2,1)은 나오지 못했지만, 비교를 할 것이라면 나와도 괜찮을 것 같습니다. 그럼 4번에도 되는지 볼까요? 어??!! 4번의 경우에도 2번의 경우랑 연관이 될 수 있네요?? 그럼 이경우는 5가 n이라고 했을 때, (n-2의 경우) + n로 표현할 수 있겠네요!! 일단 점화식 하나는 찾은 것 같습니다!
이제 두 번째로 5에서 남은 (5,4,2,1) (4,3,1)을 보면 현재와 이전의 제일 큰 두 숫자가 연속됐을 경우인 것을 볼 수 있네요? 그럼 제일 큰 두 숫자를 상수로 표현해 봅니다 +n +(n-1).. 하지만 뒤에 (2,1) (1)이 남네요.. 흠.. 고민을 하다가 다른 번호의 경우를 보니..??? 어??!! 5에서 3을 뺀 경우 2에 (2,1)이 있고 4에서 3을 뺀 경우 1에 1이 있네요?? 그럼.. (n-3의 경우) + n + (n-1)로 표현할 수 있을 까요?? 5의 (5,4,2,1)은 그렇게 표현할 수 있고 4의 경우에도 제일 큰 두 숫자가 연속됐을 경우 (4,3,1) 이 있기 때문에 표현할 수 있습니다!! 그럼 점화식을 또 하나 찾았네요!!
그러나… 세 번째로.. 아직 문제가 또 있습니다.. (n-3의 경우) + n + (n-1)로도 5의 (4,3,1) 4의 (3,2) 즉, 전 번호의 제일 큰 두 숫자가 연속됐을 경우는 표현하지 못하는 것이죠.. 근데 저희는 이미 제일 큰 두 숫자가 연속됐을 경우는 두 번째에서 구했습니다!! 이걸 어떻게 이용할 수 없을까?? 하고 처음부터 천천히 보니..??!! 첫 번째에서 최대 값이 아닌 경우를 가져와서 점화식을 표현한 것을 볼 수 있습니다!! 그럼 5의 (4,3,1)은 4의 제일 큰 두 숫자가 연속됐을 경우이니.. 혹시 n-1의 경우로 표현할 수 있을까 하고 보면 4의 (4,2,1) (3,2)는 (5,4,2,1) (5,3,2) 보다 무조건 작기 때문에 나오지 못했지만..!! 첫 번째에서 사용한 방법인 최대 값이 아닌 경우를 적용하게 되면 (4,3,1) (4,2,1) (3,2)로 n-1의 경우로 표현할 수 있게 됩니다!! 물론!! 4의 경우에도 적용이 되구요!!
이렇게 (n-2의 경우) + n, (n-3의 경우) + n + (n-1), n-1의 경우를 찾을 수 있었습니다!!
이렇게 차근차근 나열해서 찾을 수 있지만.. 시간이 오래걸릴 수도 있기 때문에 조금 더 생각이 필요하지만 더 빠른 방법인 되는 경우와 안되는 경우를 나눈 후 찾는 방법을 알아 보겠습니다!!
되는 경우를 여러가지로 나눠 찾는 방법
일단.. 되는 경우를 여러가지로 나눠 생각해 봅니다! 오른쪽 부터 큰 번호의 와인잔이라고 가정하겠습니다. O는 마실 수 있는 경우, X는 못 마실 경우로 표현하겠습니다.
마지막 와인을 먹는 경우
- OXO : 마지막 와인(n)을 먹었을 때, 그 전와인(n-1)은 먹지 않아야 그 전전 와인(n-2)을 마시더라도 연속으로 3잔을 마시지 않습니다.
- XOO : 마지막 와인(n)과 전와인(n-1)을 먹었을 때는 전전와인(n-2)을 먹지 않아야 연속으로 3잔을 마시지 않습니다.
마지막 와인을 먹지 않는 경우
-
OXOX
-
XOOX
마지막 와인(n)을 먹지 않았을 때는 전와인(n-1)의 마지막 와인을 먹는 경우와 같은 것을 볼 수 있습니다.
이제 이경우들을 점화식으로 표현해 보면
마지막 와인을 먹는 경우 1
마지막 와인(n)은 무조건 먹어야 하므로 상수로, 전 와인(n-1)은 먹지 않기 때문에 표현하지 않고, 전전 와인(n-2)은 먹을 수도 먹지 않을 수도 있기 때문에 상수가 아닌 경우의 수로 표현합니다. 즉, (n-2의 경우) + n으로 표현할 수 있습니다.
마지막 와인을 먹는 경우 2
마지막 와인(n)과 전 와인(n-1)은 무조건 먹어야 하므로 상수로, 전전 와인(n-2)은 먹지 않기 때문에 표현하지 않고, 상수인 마지막 와인(n)과 전 와인(n-1)만으로 표현할 수 없기 때문에 먹을 수도 먹지 않을 수도 있는 전전전 와인(n-3)을 상수가 아닌 경우의 수로 표현합니다. 즉, (n-3의 경우) + n + n-1로 표현할 수 있습니다.
마지막 와인을 먹지 않는 경우
마지막 와인(n)을 먹지 않는 경우 OXOX,XOOX 는 전 와인(n-1)의 마지막 와인을 먹는 경우 OXO,XOO 와 같습니다. 전 와인(n-1)의 마지막 와인을 먹는 경우라 함은, 전 와인(n-1)이 마지막 와인인 경우를 말하는 것과 같기 때문에 마지막 와인(n)을 먹지 않는 경우는 전 와인(n-1)의 마지막 와인을 먹는 경우와 같다라고 말할 수 있습니다. n-1의 경우로 표현할 수 있습니다.
확실히 하나씩 나열해서 차근차근 찾는 방법보다 되는 경우를 여러가지로 나눠 찾는 방법이 더 빨라 보이는 것을 알 수 있습니다.
내 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static Integer memo[];
static int wine[];
public static int dp(int n) {
// n < 3일 경우 인덱스가 -가 되는 것을 방지해줍니다.
if(n <= 0)
return 0;
if(memo[n] == null) {
memo[n] = Math.max(wine[n] + wine[n-1] + dp(n-3), Math.max(dp(n-1), wine[n] + dp(n-2)));
}
return memo[n];
}
public static void main(String[] args) {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
OutputStreamWriter osw = new OutputStreamWriter(System.out);
BufferedWriter bw = new BufferedWriter(osw);
try {
int n = Integer.parseInt(br.readLine().trim());
wine = new int[n+1];
memo = new Integer[n+1];
for (int i = 1; i <= n ; i++) {
wine[i] = Integer.parseInt(br.readLine().trim());
}
// 1잔인 경우와 2잔인 경우의 최대 값은 쉽게 유추할 수 있으므로 먼저 등록해줍니다.
memo[1] = wine[1];
if(n >= 2)
memo[2] = wine[1] + wine[2];
bw.write(Integer.toString(dp(n)));
bw.flush();
bw.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
참고 : https://zoonvivor.tistory.com/133
https://st-lab.tistory.com/135
해당 코드들은 저의 GitHub에서 확인할 수 있습니다.
댓글남기기