[Algorithm] cpp 백준 18186번: 라면 사기 (Large)

문제

링크: https://www.acmicpc.net/problem/18186
요약: N개 공장에서 각자 필요한 수량을 최소 비용으로 구매. 단건(B), 인접 2연속(B+C), 인접 3연속(B+2C) 구매를 조합한다.

입력/출력

1
2
3
<입력>
N B C
A1 A2 ... AN

1
2
<출력>
최소 비용

접근 개요

B≤C이면 인접 묶음이 이득이 없어 전부 단건 구매가 최적.
B>C이면 좌→우 순회하며 (a[i+1] > a[i+2])인 불균형 구간에서 2연속을 일부 먼저 적용해 3연속 적용량을 극대화.
이후 3연속 → 남은 2연속 → 단건 순으로 처리.

알고리즘

배열 a를 길이 N+2로 패딩.
i=0..N-1 순회 중:
- if a[i+1] > a[i+2]: t2 = min(a[i], a[i+1] - a[i+2]); a[i] -= t2; a[i+1] -= t2; cost += (B+C)*t2
- t3 = min(a[i], a[i+1], a[i+2]); 소진 및 비용 가산
- t2 = min(a[i], a[i+1]); 소진 및 비용 가산
- 잔여 a[i]는 단건 비용 가산

복잡도

시간: O(N)
공간: O(N)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    int n; long long B,C; if(!(cin>>n>>B>>C)) return 0; 
    vector<long long>a(n+2); for(int i=0;i<n;++i) cin>>a[i];
    long long ans=0;
    if(B<=C){
        for(int i=0;i<n;++i) ans += a[i]*B; 
        cout<<ans<<'\n'; return 0;
    }
    for(int i=0;i<n;++i){
        if(a[i+1]>a[i+2]){
            long long t2=min(a[i], a[i+1]-a[i+2]);
            if(t2>0){a[i]-=t2; a[i+1]-=t2; ans += (B+C)*t2;}
        }
        long long t3=min(a[i], min(a[i+1], a[i+2]));
        if(t3>0){a[i]-=t3; a[i+1]-=t3; a[i+2]-=t3; ans += (B+2*C)*t3;}
        long long t2=min(a[i], a[i+1]);
        if(t2>0){a[i]-=t2; a[i+1]-=t2; ans += (B+C)*t2;}
        if(a[i]>0){ ans += B*a[i]; a[i]=0; }
    }
    cout<<ans<<'\n';
    return 0;}