18185번 라면 사기 (Small)

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

Greedy 그리디 탐욕 boj 백준 복습 필수 추천 dp 수학 등차수열

무조건 3개의 공장에서 라면을 구매할 수 있는 경우가 있으면, 3개 공장을 먼저 처리하는 문제인줄 알았다.

즉, 3 → 2 → 1 이런 순서로 진행하는 줄 알았다.

하지만, 반례가 있었는데 https://www.acmicpc.net/board/view/47049

4

1 2 1 1

wrong : 13

correct : 12

1 1 1을 먼저 구매해버리면, 뒤에 하나의 공장에서 구매하는 것이 2번 일어나므로 7 + 2 * 3 = 13이 나오게 된다.

그러나, 1 1을 먼저 구매하고, 뒤이어 1 1 1을 구매하면, 5 + 7 = 12로 최소 비용을 구할 수 있게 된다.

즉, a[i + 1] > a[i + 2] 일 때는 a[i + 1] - a[i + 2]만큼의 차이와 a[i] 중 최솟값을 통해 2개의 공장에서 사는 경우를 먼저 처리해주고,

곧이어 바로 3개의 공장에서 구매할 수 있는 경우를 처리해준다.

(어차피 a[i + 1] - a[i + 2]보다 a[i]가 더 작을 때, a[i]가 0이 되는데 7 * 0 = 0이므로 상관없다.)

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 10100
 
int n, a[Max];
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
 
    int answer = 0;
 
    for (int i = 0; i < n; i++) {
        if (a[i + 1] > a[i + 2]) {
            int two = min(a[i], a[i + 1] - a[i + 2]);
            answer += 5 * two;
            a[i] -= two;
            a[i + 1] -= two;
 
            int three = min(a[i], min(a[i + 1], a[i + 2]));
            answer += 7 * three;
            a[i] -= three;
            a[i + 1] -= three;
            a[i + 2] -= three;
        }
        else {
            int three = min(a[i], min(a[i + 1], a[i + 2]));
            answer += 7 * three;
            a[i] -= three;
            a[i + 1] -= three;
            a[i + 2] -= three;
 
            int two = min(a[i], a[i + 1]);
            answer += 5 * two;
            a[i] -= two;
            a[i + 1] -= two;
        }
    
        answer += 3 * a[i];    
    }
 
    printf("%d\n", answer);
 
    return 0;
}