백준 2156 - 포도주 시식

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

2156번: 포도주 시식

이전에 풀었던 계단 오르기 문제와 유사하면서 조건은 더 적다.

 

동일한 알고리즘으로 풀었더니 계속 오답이 나왔는데, 그 이유는 이동거리의 제약 조건이 더 적었기 때문이다.

 

계단 오르기 문제는 반드시 2칸 내에서 이동해야 하는데 이번 문제는 그런 제한이 없다.

동일 알고리즘을 적용하면

100 100 1 1 100 100 의 Test case에서 100 대신 1을 고르게 된다.

따라서 이 점을 고려해 문제를 풀어야한다.

 

n번째 포도주 앞의 두 포도주를 마시거나 마시지 않는 경우는 총 4가지이다.

XX (둘 다 마시지 않음)

XO (n-1번째 포도주만 마심)

OX (n-2번째 포도주만 마심)

OO (둘 다 마심 -> n 번째는 못 마시므로 제외)

또한 마지막 값 대신 그 앞의 값을 더했을 때 최대값이 나오는 경우가 존재한다.

 

이를 활용해 Optimal substructure를 구한다.

dp[i]의 값은

i = 1 >> cost[1]

i = 2 >> cost[1]+cost[2]

i >= 3 >> max(max(dp[i-3], dp[i-2], dp[i-3] + cost[i-1]) + cost[i], dp[i-1]

                                    XX        OX        XO

 

이때 dp[i-3]은 dp[i-3] + cost[i-1]보다 반드시 작거나 같으므로 제외할 수 있다.

 

dp table을 채우고 나면 n행, n-1행 중 더 큰 값을 반환한다.

 

배운 내용 :

내가 생각했던 내용을 먼저 코드로 표현해보고 해당 코드에서 문제를 찾아 보완하는 방법을 사용하자

알고리즘만 떠올리면 코드는 금방 최적화 할 수 있다