[알고리즘] 백준 2156번: 포도주 시식 (C++), 솔루션 없음

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

여전히 DP 문제는 접근하기 어렵다. 문제를 풀 때마다 '이렇게 생각해보자'라는 지난 DP 문제로부터 나름대로 얻은 팁을 적용해봐도 어렵다.

 

이제까지 접근했던 방식들을 떠올려보면 직접 TC를 가지고서 output을 노트에 도출하며 관계성과 점화식을 세웠었다.

[input]
6
6
10
13
9
8
1
[answer]
33

 

맨 처음에는 조금 멍청하게 접근을 했는데

n번째 포도주를 선택한다고 했을 때, 연속적으로 2개를 그림으로 고른 것 중에 최댓값을 구하면 될 거라고 생각했다.

[이것이 안 되는 이유]

1. 한 칸 마시고, 한 칸 건너뛰고, 한 칸 마신 경우도 최댓값이 될 수 있다.
2. 꼭 n번째 포도주를 마신 게 최댓값을 도출하지 않는다. 왜냐하면, 그 전 n - 1, n - 2의 포도주를 연속으로 마시는 것도 최댓값을 만들 수 있기 때문이다.

---

이번 문제의 접근 방식

DP는 아무리 풀어도 접근 방식이 참 어렵다. 다른 알고리즘 응용문제들과 달리 아예 프레임부터 늘 다른 느낌이라 개념을 제외하고는 매일 낯설다.

 

직접 노트에 TC를 구현하다 보니 1번째, 2번째, 3번째,..., n - 1번째, n번째 와인까지를 구해도 관계성을 찾을 수 없었다.

(+참고 1 https://yabmoons.tistory.com/512)

(+참고 2 https://debuglog.tistory.com/80)

>> 참고 1은 경우들을 다 따지고, 참고 2는 조금 수학적(?)으로 접근한다. 무엇이 더 낫다고 말하지 않는 이유는 둘 다 도움이 되었기 때문이다. 참고 1은 직접 블로그 필자분께서 경우들을 따지면서 이해를 도와주셨고, 참고 2는 그 이해한 내용을 가지고서 왜 그런 점화식이 나오는지 이해를 도우셨다.

 

[참고 1]

참고한 포스팅에서는 두 가지 포인트가 있었다.

 

1. [조건] 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

다음 조건을 가지고서

1. 0번 연속으로 마셨을 때
2. 1번 연속으로 마셨을 때
3. 2번 연속으로 마셨을 때

다음 경우들을 따진다. '0번 연속으로 마셨을 때'는 무슨 소리냐면 현재 i번째 와인을 마시지 않고, 최댓값이 나오는 경우를 말한다.

 

2. 그전에 어떻게 마셨든 상관없다.

이건 아마 필자인 나만 느꼈을 포인트였을 거 같다. 왜냐하면 이때까지 점화식을 도출할 때, 관계가 안 밝혀지니 매번 전체를 직접 노트에 구현했기 때문이다. 나름의 모집단(?) 같은 느낌으로 전에 어떻게 마셨든 상관없으니 모집단에만 집중을 하자.

>> 관계성을 파악하지 못하는 이유는 방금 어렴풋이 느꼈다. 사람이기에 무의식적으로 최댓값을 적고 있는 스스로를 볼 수 있었다. 무슨 말이냐면 사람이라면 아무 생각 없이 '이게 최댓값이야'하고 적어내는데, 컴퓨터는 '왜? 이 경우도 있고, 이런 경우도 있고 얼마나 많은데 그게 왜?'라고 말하는 것과 같다. 사람의 무의식이 참 무서워진 순간이다.

 

[참고 2]

참고 2는 직접 링크를 걸어둔 곳을 찾아 들어가 꼭 보았으면 좋겠다. 저렇게 간단하게 정리가 될 수 있을까를 보고 감탄했다. 저런 식을 도출하면서 반례가 발생할까 두렵지 않으셨을까, 저런 컴퓨팅 사고가 너무 부러웠다.

 

3번 포도주까지만 따졌을 뿐인데 저 점화식이 나온 것이 정말 감탄스럽다. 나였으면 4번까지 따지고, 1번 포도주는 어쩌나 고민하다가 또 굴레에 빠졌을 것이다.

 

어쩜 적절한 곳에서 '이건 메모이제이션 된 최댓값을 가져오는 거야'라는 생각을 하셨을까

---

이번 포스팅에서는 솔루션을 적어두고 싶지 않다. DP의 감각을 좀 더 기르고 나서 업 솔빙을 할 때, 그때의 내가 확실하게 스스로 풀었다면 그때 포스팅을 올리고 싶다.

 

참고 2 블로그는 두고두고 봐야겠다.