[백준] 18185: 라면 사기(Samll)

GitHub: https://github.com/tyt0815

tyt0815 - Overview

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

18185번: 라면 사기 (Small)

라면 사기

솔브드 기준 다이아5문제 입니다. 지인이 물다이아 문제라면서 추천해 줬는데 저는 어려웠습니다... 내용은 그리디 혹은 DP문제라 볼 수 있는데, 한가지 예외를 정확히 이해하면 풀 수 있습니다.

참고로 출제자분의 블로그에 문제 해설이 되어 있는데 저는 이걸 보고 풀었습니다.

https://youngyojun.github.io/contest/review/2020/02/15/iamcoder-2019-yearend-contest/

나는코더다 2019 송년대회 이야기

일단 조건에서, 한곳에서 사는경우, 두곳에서 사는경우, 세곳에서 사는 경우로 나뉘고 각각 3원, 5원, 7원의 가격이 책정되었습니다. 바꿔 표현하면 3, 3+2, 3+2+2이고 3을 B, 2를 C라고 표현하면 B, B+C, B+2C입니다. 이를 각각 Case1, Case2, Case3라 하겠습니다.

B와 C로 나누어 설명하는 이유는 Case2, 3의 경우 첫번째 공장에서 B의 가격으로 라면을 사고, 두번째 공장, 세번째 공장에서는 C의 가격으로 구매했다고 생각하기 위해서 입니다. 즉 3개를 할인받은 가격에 사는 것이 아닌 연속된 공장에서 구매하면 두번째 공장부터는 할인된 가격 C에 살 수 있다는 개념입니다. 이제부터 B와 C의 계수를 모두 더하면 총 구매한 라면의 갯수가 됩니다.

 

가장 핵심적인 예외인데 4개의 라면공장에서 2, 3, 1, 1개를 스택형식으로 표현한 것 입니다. 여기서 Case3는 두가지가 있을 수 있는데, 1~3공장에서 사는 경우와 2~4공장에서 사는 경우 입니다. 각각을 계산해 보면

1~3는  Case1 2개, Case2 1개, Case3 1개로 총 4B + 3C = 18이고

2~4는 Case1 0개, Case2 2개, Case3 1개로 3B + 4C = 17이므로

2~4공장에서 Case3를 취한게 싸다는 걸 알 수 있습니다. 그리디하게 취해선 예외상황에서 틀리게 되는 거죠.

1~3에서 Case3 를 취할 경우

2~4에서 Case3를 취할 경우

핵심은 앞쪽에서 미리 Case3를 취하면 뒤쪽에서 Case3를 취할수 없다는 것과 그 결과 더 비싼 가격이 될 수 있다는 겁니다. 이 점을 유의해서 출제자의 풀이를 한번 보겠습니다.

앞서 말했던 것 처럼 Case1, Case2, Case3를 한번에 3, 5, 7로 처리하는게 아니라, 연속적으로 구매할 경우 할인을 받아 구매하는 형식으로 구현되어 있습니다. 위 글과 그림들을 이해하고 출제자의 풀이를 보면 왜 B+C 즉 Case2부터 하게 되는지 이해 할 수 있을거라 생각합니다.

#include <iostream>
#define B 3
#define C 2

using namespace std;

typedef struct
{
    int b;
    int c;
    int c2;
}ramen;


void printAry(int* ary, int end)
{
    for(int i = 0; i < end; ++i) cout << ary[i] << " ";
    cout << endl;
}

int main()
{
    int n, value = 0;
    ramen *amount;
    cin >> n;
    amount = new ramen[n];
    for(int i = 0; i < n; ++i)
    {
        cin >> amount[i].b;
        amount[i].c = amount[i].c2 = 0;
    }

    for(int i = 0; i < n - 1; ++i)
    {
        int update_amount = min(amount[i].b, amount[i+1].b);
        amount[i+1].b -= update_amount;
        amount[i+1].c += update_amount;
        if(i > 0)
        {
            update_amount = min(amount[i].c, amount[i+1].b);
            amount[i+1].b -= update_amount;
            amount[i+1].c2 += update_amount;
        }
    }

    for(int i = 0; i < n; ++i)
    {
        value += amount[i].b * B + amount[i].c * C + amount[i].c2 * C;
    }

    cout << value;

    return 0;
}

문제의 알고리즘 분류가 그리디로 되어 있는데 풀이를 보면 DP가 더 맞는거 같네요.