[C++] 백준 2156번 포도주 시식

다이나믹 프로그래밍 문제.

처음 문제를 보고 예전에 풀었던 계단 오르기와 비슷한 문제라고 생각했다.

[C++] 백준 2579번 계단 오르기

 

그런데 막상 문제를 풀어보니 엄청 많이 틀렸고, 반례들을 통해 잘못된 점을 알게됐다.

 

문제 접근방식

우선 조건으로 주어지는 건 간단하다. 최대한 많은 양을 먹어야 하고 3잔을 연속으로 먹는 건 불가능하다.

천국의 계단 같은 경우는 어차피 +1 아니면 +2였기 때문에 이 문제도 똑같은 방식으로 접근했다.

이 두 개 조건을 가지고 문제를 풀려했다.

처음 작성한 코드

 

그리고 결과는 틀렸습니다 였다.

 

계단 오르기 문제가 실버3이고 이 문제가 실버1 문제인데 같은 로직이면 이상한게 당연한 것 같아보이기는 했다.

그래서 반례들을 찾기 시작했다.

 

처음 찾은 반례는

10 0 0 10 0 5 10 0 0 1 10

이 케이스의 출력은 36이 나와야 하는데, 나는 35가 나왔다.

케이스를 보니, 0이 들어가면 어차피 안 마신 것과 같으므로 만일 i번째에서 i-2번째가 0이라면

그냥 바로 이전(i-1)의 최대값을 그냥 더하는 식으로 구현해봤다.

 

두번째 시도의 코드

이번에도 틀렸습니다 가 나왔다.

뭐가 문제인지 도저히 못 찾겠어서 다른 반례를 찾았다.

 

6 1000 1000 1 1 1000 1000

이 케이스의 답은 4000이다. 나는 3001이 나왔다.

그래서 그림을 그려보면서 고려해 보았더니 다음과 같은 해답을 얻었다.

이 문제는 계단식 문제처럼 무조건 +1 또는 +2할 필요는 없는 문제였다.

2개를 건너뛸 수도 있는 조건을 생각하지 못했다.

이 때, 3개부터는 어차피 건너뛰는 것이 손해이므로 고려해줄 필요가 없다.

그래서 i번째의 최대값을 구할 때, i-1번째가 2개 이전에서 온 경우도 고려해 주고 비교대상에 올렸다.

따라서 비교를 해야하는 대상들은 다음과 같다.

 

i번째까지 오는데 최대로 마실 수 있는 양의 경우의 수는 다음과 같다. (이 중 최대값을 구해야 한다.)

1. i번째에서 2개 전에서 왔을 때, dp[i - 2] + wine[i]
2. 바로 이전(i - 1)번째가 2개 전에서 왓을 때, dp[i - 3] + wine[i - 1] + wine[i]
3. 바로 이전(i - 1)번째가 3개 전에서 왔을 때, dp[i - 4] + wine[i - 1] + wine[i]

이것들 중에 최대값을 구해서 출력하면 된다.

 

사용한 STL과 변수

max 메서드를 사용하기 위해 <algorithm> STL을 사용했다.

그리고 입력받는 정수 n, 결과값 result, 와인의 양을 담을 배열 wine과

각 와인잔의 번째까지 올 때 최대로 마실 수 있는 양을 저장할 배열 dp를 만들었다.

 

메인함수

n을 입력받고 와인잔에 있는 와인의 양을 입력받는다.

dp[1]과 dp[2]는 각각 첫번째 잔의 양과 첫번째 잔 + 두번째 잔의 양과 같으므로 초기화 해준다.

그리고 result 변수를 dp[2]로 초기화 해준다.(dp[2]가 최대값일 수도 있으므로)

그리고 dp의 i번째를 위에서 고려해준 3가지 경우에서 최대값으로 만들어주고,

result에 저장된 값과 비교해서 더 큰값이라면 업데이트 해준다.

 

정답률이 처참한 문제였는데, 왜 그런지 이유를 알 수 있었던 문제였다.

테스트 케이스가 조금만 더 많았다면 맞출 수 있었을 것 같은데 아쉽다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.