[백준 / BOJ] C++ 18185 라면 사기 (Small)

18185번: 라면 사기 (Small)

 

문제

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

18185번: 라면 사기 (Small)

 

 

풀이

처음에는 앞에서부터 최대한 많이 3군데 연속해서 구매하고, 다시 앞에서부터 2군데, 그리고 낱개를 구매하도록 했으나 WA를 받았다. 2~3시간 정도 고민하다가 질문 게시판에서 반례 테스트 케이스를 얻어 2시간 정도 더 고민하고서야 풀었다.

 

0번 공장부터 차례대로 방문하며 아래 과정을 거친다.

 

1. i, i+1, i+2번째 공장에서 모두 라면을 구매할 수 있는 경우 (0 ≤ i ≤ n-3)

  1) 구매할 수 있다면 i+1번째 공장에서 구매할 양이 i+2번째 공장에서 구매할 양보다 많은 경우

     - i+1번째 공장부터 i+3번째 공장까지 고려했을 때 3군데에서 구매할 가능성을 남겨둔다.

     - 가능성을 남겨둘 만큼만 제외하고 최대한 2군데에서 구매한다.

  2) 그렇지 않은 경우

     - 최대한 많이 3군데 연속해서 구매한다.

2. 위 과정이 끝나면 남은 i번째 공장의 라면을 모두 낱개로 구매한다.

3. n-2, n-1번 공장은 최대한 많이 2군데 연속으로 구매한 다음, 남은 것만 낱개로 구매한다.

 

이렇게 하면 최소한의 비용으로 모든 라면을 구매할 수 있게 된다.

 

 

코드

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

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