[백준] 라면 사기 small

문제 링크

1. 문제 설명

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

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

i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.
i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다.
최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

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

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

출력
첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.

2. 문제 접근

문제를 처음 봤을 땐 DP 문제인 줄 알았지만, 라면 공장의 최대 개수가 $10^4$개이므로 각각의 선택지마다 라면을 한 개, 두 개, 또는 세 개를 산다는 선택지를 모두 고려해 버리면 $O(n^3) = 10^{12}$만큼 시간이 걸리므로 시간 초과가 됩니다.

라면을 한 개를 사면 3원, 두 개를 사면 5원, 세 개를 사면 7원입니다. 언뜩 보면 세 개를 사면 평균 가격이 가장 낮기 때문에 3개를 최대한 많이 사면 정답이지 않을까 싶습니다. 그렇게 해서 앞에서부터 세 개씩 최대한 사면 되지 않을까 싶지만 쉬운 반례가 있습니다. [1 2 1 1] 을 앞에서 세 개를 사 버리면 [0 1 0 1] 이 되어 13원이 들지만 앞에서 두 개, 뒤에서 세 개를 사면 12원으로 해결할 수 있습니다.

라면을 한 개를 사면 3원, 두 개를 사면 하나는 3원 + 다음 하나는 2원, 세 개를 사면 하나는 3원 + 다음 두 개는 2원입니다. 핵심은 어떻게 하면 최대한 많은 3원 단가의 라면을 2원에 구매할 수 있을까 입니다.

배열을 길이 3 기준으로 살펴보겠습니다. 가장 앞의 원소들은 어쩔 수 없이 3원으로 사야 하는 라면들입니다. 가운데 라면들을 최대한 많이 앞의 라면들과 같이 구매해 2원으로 구매하는 최선의 방법을 찾아야 합니다.

가운데 원소의 크기가 마지막 원소의 크기보다 작다면 두 가지 방법으로 앞에서부터 처리해주면 됩니다.

1. list[i] < list[i + 1] < list[i + 2] : list[i]개만큼 3개를 최대한 합니다. 나머지 부분은 뒤의 원소를 조회하며 판단합니다. 예를 들어 [1 2 3] 일때, [1 1 1] 만큼 산 다음 [0 1 1] 은 다음에 뒤의 원소를 받아서 어떻게 구매할 지 판단할 수 있습니다.

2. list[i] > list[i + 1] < list[i + 2] : list[i + 1]개만큼 3개를 최대한 사고 배열 앞의 list[i] - list[i + 1]개는 2개씩 혹은 개별로 삽니다. 예를 들어 [2 1 3] 이라면 [1 1 1] 후 앞의 1개를 개별 구매하게 됩니다.

가운데 원소의 크기가 마지막 원소의 크기보다 클 때는 앞에서부터 처리하는 식으로 처리할 수 없습니다. 가운데 원소를 최대한 두 개 도는 세 개로 묶을 방법을 찾아야 합니다.

1. list[i] > list[i+1] - list[i+2] : 마지막 원소가 충분히 큰 경우입니다.
   예제 배열이 [4 5 3] 일때, 앞에서 2개씩 2개를 사서 [2 3 3] 이 되면 3개씩 2번 구매합니다. 나머지 [0 1 1] 은 바로 처리하지 않고 뒤의 원소를 조회하며 판단합니다.
2. list[i] < list[i+1] - list[i+2] : 마지막 원소가 매우 작은 경우입니다.
   [3 5 1]일때, 앞에서 [3 3] 만큼 3개씩 2개를 구매한 뒤 [0 2 1]은 뒤의 원소를 조회하며 판단합니다.

쉽게 생각하면 배열을 길이 3 단위로 순회하면서 두 번째 라면을 가능한 한 많이 첫 번째 라면과 묶어서 처리하는 작업이라고 생각할 수 있습니다.

3. 문제 풀이

1. 자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] li = new int[n + 2];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            li[i] = Integer.parseInt(st.nextToken());
        }
        li[n] = 0;
        li[n + 1] = 0;

        int ans = 0;

        for (int i = 0; i < n; i++) {
            if (li[i + 1] > li[i + 2]) {
                int a = Math.min(li[i], li[i + 1] - li[i + 2]);
                ans += 5 * a;
                li[i] -= a;
                li[i + 1] -= a;

                int b = Math.min(li[i], Math.min(li[i + 1], li[i + 2]));
                ans += 7 * b;
                li[i] -= b;
                li[i + 1] -= b;
                li[i + 2] -= b;
            } else {
                int b = Math.min(li[i], Math.min(li[i + 1], li[i + 2]));
                ans += 7 * b;
                li[i] -= b;
                li[i + 1] -= b;
                li[i + 2] -= b;

                int a = Math.min(li[i], li[i + 1]);
                ans += 5 * a;
                li[i] -= a;
                li[i + 1] -= a;
            }

            ans += 3 * li[i];
        }

        System.out.println(ans);
        br.close();
    }
}

2. 파이썬 코드

n = int(input())
li = list(map(int, input().split())) + [0,0]
ans = 0

for i in range(n): 
    if li[i + 1] > li[i + 2]:
        a = min(li[i], li[i + 1] - li[i + 2])  
        ans += 5 * a
        li[i] -= a
        li[i + 1] -= a

        b = min(li[i], li[i + 1], li[i + 2])  
        ans += 7 * b
        li[i] -= b
        li[i + 1] -= b
        li[i + 2] -= b


    else: 
        b = min(li[i], li[i + 1], li[i + 2]) 
        ans += 7 * b
        li[i] -= b
        li[i + 1] -= b
        li[i + 2] -= b

        a = min(li[i], li[i + 1])
        ans += 5 * a
        li[i] -= a
        li[i + 1] -= a

    ans += 3 * li[i]
print(ans)