백준 18186 라면 사기 (Large)

18186번: 라면 사기 (Large)

이 문제는 18185번을 풀면 바로 풀 수 있는 문제이다.

라면 개수에 따른 비용이 등차수열을 이룬다는 특징이 있다. 이를 통해 1개 혹은 3개를 구매할 때 가장 싸게 살 수 있고, 2개를 구매하는 것이 1개 혹은 3개를 구매하는 것 보다 금액이 많이 필요하다는 것을 알 수 있다.

따라서 가장 가치가 있는 구매 방법을 b, c에 따라 나눌 수 있다.

1.  b <= c일 때 
   모든 라면을 한번에 한 개씩 구매하는 것이 최소 금액이다.
2.  b > c일 때
   세개를 연속해서 구매하는 횟수가 많을수록 필요한 금액이 적어지는 경우이다.

b <= c일 때는 총합에 b를 곱해서 간단하게 풀 수 있다.

b > c일 때를 고민해야 한다. 필자는 연속하여 존재하는 라면의 개수를 seq배열에 담고, 연속한 두 라면의 개수 중 작은 것에 dir을 표시해 앞에서 무작정 3개를 연속해서 구매했다가 뒤에서 오히려 연속된 3개를 구매하지 못하는 경우의 수를 막았다.

하지만 핵심적인 부분을 놓쳤는데, a[i+1] > a[i+2]인 경우이다. 이때는 a[i+1] - a[i+2] 만큼 a[i]와 a[i+1](2개)을 구매하고, 이후에 남은 라면에서 구매할 수 있는 연속된 3개의 최대치를 구매해야 한다. 처음에 고안했던 코드는 이를 만족하지 않았고, 이를 고려하여 seq배열과 dir을 사용하지 않는 간결한 코드로 AC를 받았다.

비록 온전히 내 힘으로 풀지는 못했지만, 3시간 정도 고민해서 정답에 근접했다는 점에서 의의가 있다고 생각한다.

 #include<bits/stdc++.h>
 using namespace std;
 const int N = 1e6 + 5;
 typedef long long ll;
 ll n, b, c, a[N], ans;
 int main()
 {
     cin >> n >> b >> c;
     for(int i=0; i<n; i++) cin >> a[i];
     ll left = b, mid = b + c, right = b + 2 * c;

     if(b <= c)
     {
         for(int i=0; i<n; i++)
            ans += a[i] * left;
     }
     else
     {
         for(int i=0; i<n; i++)
         {
             if(a[i] == 0) continue;
             if(a[i+1] > a[i+2])
             {
                 ll cur = a[i+1] - a[i+2];
                 if(a[i] <= cur)
                 {
                     ans += a[i] * mid;
                     a[i+1] -= a[i], a[i] = 0;
                 }
                 else
                 {
                     ans += cur * mid;
                     a[i] -= cur, a[i+1] -= cur;

                     ll small = min(a[i], a[i+1]);
                     ans += small * right;
                     a[i] -= small, a[i+1] -= small, a[i+2] -= small;
                 }
             }
             else
             {
                 ll small = min(a[i], a[i+1]);
                 ans += small * right;
                 a[i] -= small, a[i+1] -= small, a[i+2] -= small;
             }
             ans += a[i] * left;
         }
     }
     cout << ans;
 }