[백준 / BOJ] C++ 18186 라면 사기 (Large)

18186번: 라면 사기 (Large)

 

문제

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

18186번: 라면 사기 (Large)

 

 

풀이

[백준 / BOJ] 18185 라면 사기 (Small) 문제 / [백준 / BOJ] 18185 라면 사기 (Small) 풀이

위 문제를 먼저 풀고 난 후 풀면 비교적 쉽게 풀 수 있다. 위 문제와의 차이점은 1군데, 2군데, 3군데 구매했을 때 가격이 3, 5, 7이 아니라 b, b+c, b+2*c 라는 것이다. 즉, 위 문제는 이 문제에서 b = 3, c = 2 일 때가 된다.

 

위 문제는 길게 연결된 공장에서 구매할수록 적게 연결된 공장보다 싸게 구매할 수 있다. 그러나 그렇지 않은 경우는 굳이 연결된 공장에서 구매할 필요 없이 낱개로 구매하는게 더 싸게 구매할 수 있다.

 

따라서 b > c인 경우 위 문제에서 한 것과 동일하게, 그렇지 않은 경우 (구매할 라면의 수 총 합) * b를 출력하면 된다.

총 수를 구할 때 long long을 써야한다. 단, for문으로 일일이 더해줘야 한다. (accumulate 함수로 vector의 원소들 모두를 더하는 방법은 return 값이 int라 안됨)

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, b, c, ans = 0, cnt;
  cin >> n >> b >> c;
  vector<int> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  if (b < c) {
    for (int i = 0; i < n; i++)
      ans += v[i];
    ans *= b;
  } else {
    for (int i = 0; i < n - 2; i++) {
      while (v[i] && v[i + 1] && v[i + 2]) {
        if (v[i + 1] > v[i + 2]) {
          cnt = min(v[i], v[i + 1] - v[i + 2]);
          v[i] -= cnt;
          v[i + 1] -= cnt;
          ans += (b + c) * cnt;
        } else {
          cnt = min(v[i], v[i + 1]);
          v[i] -= cnt;
          v[i + 1] -= cnt;
          v[i + 2] -= cnt;
          ans += (b + 2 * c) * cnt;
        }
      }
      ans += b * v[i];
      v[i] = 0;
    }
    cnt = min(v[n - 2], v[n - 1]);
    ans += (b + c) * cnt;
    v[n - 2] -= cnt;
    v[n - 1] -= cnt;
    ans += b * (v[n - 2] + v[n - 1]);
  }
  cout << ans;
  return 0;
}