BOJ 2156번 - 포도주 시식
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
정말 기초적인 dp 문제인데 반례를 한참 동안 못 찾아서 반성할 겸 포스팅한다.
다음과 같은 배열 A를 정의하자.
A[i] = i번째 포도주의 양
다음과 같이 점화식을 세우면 WA를 받는다.
dp[i] = max(dp[i - 2], dp[i - 3] + A[i - 1]) + A[i];
사실 이 점화식은 2579번과 동일한 점화식이다.
2579번에서는 i번째 계단을 밟기 전에 (i - 1)번째 또는 (i - 2)번째 계단을 반드시 밟아야 한다는 조건이 있다.
하지만 이 문제에서는 그러한 제한이 존재하지 않는다.
따라서 아래와 같은 경우가 발생한다.
O O X X O O
위의 점화식에서는 이러한 경우를 제대로 처리하지 못한다.
다음과 같이 점화식을 변형할 수 있다.
dp[i] = max(dp[i - 1], max(dp[i - 2], dp[i - 3] + A[i - 1]) + A[i]);
두 점화식의 차이를 살펴보자.
첫 번째 점화식에서 dp[i]는 [1 .. i]번째 포도주 잔에서 i번째 포도주 잔을 반드시 선택할 때 포도주 양의 최댓값이다.
두 번째 점화식에서 dp[i]는 [1 .. i]번째 포도주 잔에서 포도주 양의 최댓값이다.
미묘한 차이가 AC를 결정 짓는다.
실버 문제(그것도 well-known 문제)에 당해 버렸다.
반성하면서 끝