[BaekJoon] 18185번 - 라면 사기 (Small) [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 세 가지 방법을 통해 모든 라면을 구매하는 최소 비용을 구하는 문제로 그리디 알고리즘을 활용하면 해결할 수 있다. 각 방법을 통해 구매한 라면의 평균 가격을 보면 첫 번째 방법은 1개당 3원이 들고, 두 번째 방법은 1개당 2.5원이 들고, 세 번째 방법은 1개당 2.33원이 들어서 최대한 세 번째 방법으로 구매하고 아니면 두 번째 방법으로 구매해야 하는 것처럼 보인다. 하지만 1 2 1 1로 라면이 주어질 경우 이런 방식으로 구매하면 첫 번째 공장에서 7원에 구매 후 0 1 0 1이 남게 되고 각 라면을 3원에 구매하면 총 구매 비용은 13원이 된다. 하지만 첫 번째 공장에서 두 번째 방법으로 라면을 구매하면 5원을 사용해서 0 1 1 1을 만들 수 있고 이후 두 번째 공장에서 7원을 사용하면 12원으로 모든 라면을 구매할 수 있다.

포인트는 각 라면은 3원을 주고 구매되거나 이전 공장에서 3원을 주고 구매한 라면과 세트로 구매해서 2원에 구매하거나 전전 공장에서 3원을 주고 구매한 라면과 이전 공장에서 2원을 주고 구매한 라면과 세트로 구매해서 2원에 구매하는 세 가지 경우가 존재하는 것으로 모든 공장에 대한 각각의 라면 수를 $a$, $b$, $c$로 두었을 때, 총 구매 금액은 $3 \times a + 2 \times (b + c)$ 가 되며 $a + b + c$ 가 일정하므로 $a$ 를 최대한 줄이면 된다.

$i$ 번 공장에서 3원을 주고 산 라면의 수를 $x$, $i - 1$ 번 공장에서 3원을 주고 산 라면과 세트로 $i$ 번 공장에서 2원을 주고 산 라면의 수를 $y$, $i - 2$ 번 공장에서 3원을 주고 산 라면과 $i - 1$ 번 공장에서 2원을 주고 산 라면과 세트로 $i$ 번 공장에서 2원을 주고 산 라면의 수를 $z$ 라고 하면 $i + 1$ 번 공장에 라면이 $k$ 개 있을 때 각 라면은 $i + 1$ 번 공장에서 3원을 주고 구매하거나, $i$ 번 공장에서 3원을 주고 구매한 라면과 세트로 2원에 구매하거나 $i - 1$ 번 공장에서 3원을 주고 구매한 라면과 $i$ 번 공장에서 세트로 2원을 주고 구매한 라면과 세트로 2원에 구매를 할 수 있다. 첫 번째 방법은 3원에 구매한 라면의 수를 늘리는 것이므로 나머지 두 방법이 안될 때 적용하면 되며 두 번째 방법과 세 번째 방법은 당장의 금액은 동일하지만 두 번째 방법을 적용하면 $i + 2$ 번 공장에서 2원으로 라면을 구매할 수 있는 세 번째 방법을 확보할 수 있지만 세 번째 방법을 적용하면 $i + 2$ 번 공장에서 2원으로 라면을 구매할 수 있는 세 번째 방법을 확보할 수 없다. 따라서 두 번째 방법, 세 번째 방법, 첫 번째 방법 순서로 적용하는 것이 $i + 1$ 번 공장에서 항상 최적의 선택이 된다.

해당 문제 출제자인 yclock님 블로그 나는코더다 2019 송년대회 이야기에 위 로직이 잘 설명되어 있다.

---

2. 코드

1. 풀이 [Java]

앞에 패딩을 두 칸 주어서 인덱스 처리를 간단하게 했다.

import java.io.*;
import java.util.*;

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

        int n = Integer.parseInt(br.readLine());
        int[][] cnt = new int[2 + n][3];

        st = new StringTokenizer(br.readLine());
        for (int i = 2; i < 2 + n; i++) {
            int x = Integer.parseInt(st.nextToken());
            int[] prev = cnt[i - 1];

            if (x >= prev[0]) {
                cnt[i][1] = prev[0];
                x -= prev[0];
            } else {
                cnt[i][1] = x;
                continue;
            }

            if (x >= prev[1]) {
                cnt[i][2] = prev[1];
                x -= prev[1];
            } else {
                cnt[i][2] = x;
                continue;
            }

            cnt[i][0] = x;
        }

        int sum = 0;
        for (int[] row : cnt) {
            sum += 3 * row[0] + 2 * (row[1] + row[2]);
        }

        System.out.println(sum);
    }
}

2. 풀이 [C++]

앞에 패딩을 두 칸 주어서 인덱스 처리를 간단하게 했다.

#include <bits/stdc++.h>
using namespace std;

int cnt[10002][3];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 2; i < 2 + n; i++) {
        int x;
        cin >> x;

        if (x >= cnt[i - 1][0]) {
            cnt[i][1] = cnt[i - 1][0];
            x -= cnt[i - 1][0];
        } else {
            cnt[i][1] = x;
            continue;
        }

        if (x >= cnt[i - 1][1]) {
            cnt[i][2] = cnt[i - 1][1];
            x -= cnt[i - 1][1];
        } else {
            cnt[i][2] = x;
            continue;
        }

        cnt[i][0] = x;
    }

    int sum = 0;
    for (int i = 2; i < 2 + n; i++) {
        sum += 3 * cnt[i][0] + 2 * (cnt[i][1] + cnt[i][2]);
    }

    cout << sum;
}

---