BOJ 18185 라면 사기 (Small)

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

18185번: 라면 사기 (Small)

문제

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).

교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.

최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N가 주어진다.

두번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.

풀이

발상의 전환이 중요한 문제이다. 처음에는 두번째와 세번째의 방법을 두개의 또는 세개의 연속된 공장에서 라면을 구매하는 것으로 생각해 애먹었지만 문제에서 주어진 그대로 생각하면 된다.

두번째 방법은 이웃한 두 개의 공장에서 라면을 구매하는 데 5원이 든다는 말이지만, 첫번째 방법을 빼면, "어떤 공장에서 라면을 구매하는 데 그 이전 공장에서 3원을 주고 라면을 구매했다면 그 건수 하나당 2원에 구매할 수 있다"라고 해석할 수 있다. 마찬가지로 세번째 방법을 "어떤 공장에서 라면을 구매하는데 그 이전 공장에서 두번째 조건에 해당하는 2원에 구매한 라면 하나당 2원에 또 구매할 수 있다"라고 해석할 수 있다.

관점을 바꿔서 어떤 공장에서 라면을 구매하는 가격을 책정하는 문제로 바꿔보자. 한 공장에서 라면을 구매하는 방법은 3원을 주고 구매하는 방법과 특정 조건이 만족되면 2원을 주고 구매하는 방법의 두 방법 뿐이다. 당연히 한 공장에서 라면을 구매하기 위해서는 2원에 구매할 수 있는만큼 구매하는 것이 최적해이다.
첫번째 공장에서는 이전 공장이 하나도 없으므로 무조건 3원에 라면을 모두 구매해야 한다. 따라서 유일한 방법인 3원에 모두 구매하는 것이 최적해이고, 이후에 다른 공장에서 구매하는 것과 관계없다. 두번째 공장에서는 최대 첫번째 공장에서 3원에 구매한 라면의 수만큼 2원에 구매할 수 있고, 나머지는 모두 3원에 구매해야 한다. 두번째 공장에서 3원에 구매했거나, 첫 번째 공장에서 3원에 구매한 것을 토대로 두 번째 공장에서 2원에 구매한 개수만큼 세 번째 공장에서 2원에 구매할 수 있다.
세 번째 공장 이후의 2원에 구매할 수 있는 라면의 최대 개수는 i번째 공장에 대해 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수가 된다.
좀더 일반적으로 두 번째 공장의 경우 i-2번째 공장에서 구매한 라면의 총 개수가 0이라 두면 동일한 계산이 되고, 첫 번째 공장도 i-1, i-2번째 공장에서 라면을 0개 구입한 것과 동일하다.

따라서 존재하지 않는 공장에서 구매한 개수를 0이라 강제하고 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수를 이용해 DP를 돌리는 것으로 해결 가능하다.