정올 2194 요플레 공장 문제풀이

정올 문제풀이

2194 : 요플레 공장

 

 

언제나 문제를 이해하는 데 시간이 더 걸린다 ㅡㅡ^

각 주마다 필요한 우유를 언제 사두는게 더 싼지 구하는 문제다

 

c++ 제출코드 (변수선언을 상단으로 올리면 c 제출가능)

#include <stdio.h>

int main()
{
    int n, s;
    int arr[10000][2];

    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++)
        scanf("%d %d", arr[i], &arr[i][1]);

    int price = arr[0][0];
    unsigned long long result = 0;

    for (int i = 0; i < n; i++)
    {
        price += s;
        if (price > arr[i][0])
            price = arr[i][0];

        result += price * arr[i][1];
    }

    printf("%llu\n", result);

    return 0;
}

 

입력이 다음과 같을 경우

4 5
88 200
89 400
97 300
91 500

 

일단 우유는 절대 상하지 않는다 ㅎㅎ

 

n = 4, 4주

s = 5, 1주동안 1L의 우유를 보관하는데 필요한 비용

1주차 : 우유 1L에 88원이고 200L가 필요하다

2주차 : 우유 1L에 89원이고 400L가 필요하다

3주차 : 우유 1L에 97원이고 300L가 필요하다

4주차 : 우유 1L에 91원이고 500L가 필요하다

 

1주차에 필요한 우유는 200L이고 리터당 88원에 구입한다

17600원

 

2주차에 필요한 우유는 400L이고 리터당 89원에 구입한다

35600원

만약 1주차에 리터당 88원으로 더 싸다고 먼저 구입했을 경우는

88 * 400 + 보관료 5 * 400 = 37200원으로 더 비싸다

 

3주차에 필요한 우유는 300L이고 리터당 94원에 구입한다

28200원

94원이 나온 이유는 2주차 우유값 89원 + 1주 보관료 5원 = 94원

89 * 300 + 5 * 300 = 28200

=> 94 * 300 = 28200

3주차 우유값이 97원으로 300L 구입시 29100원이니까 2주차에 구매해서 보관하는 비용이 더 싸다

 

4주차에 필요한 우유는 500L이고 리터당 91원에 구입한다

45500원

 

17600 + 35600 + 28200 + 45500 = 126900

126900원이 최소비용이 된다

 

 

 

다른 입력 예를 생각해보자

5, 10

15 100

26 100

37 100

46 100

54 100

 

1주차는 무조건 구매 15 * 100 = 1500원

2주차는 (15 + 10) * 100 = 2500원

3주차는 (25 + 10) * 100 = 3500원

4주차는 (35 + 10) * 100 = 4500원

5주차는 54 * 100 = 5400원

그래서 최소비용 17400원