[백준 13305] 주유소

www.acmicpc.net/problem/13305

13305번: 주유소

그리디를 사용하는 문제이다.

 

처음엔 뒤에서 부터 접근했는데 그렇게 해선 못푼다 ㅠ

왜냐면 처음부터 현재 시점 사이에서 가장 작은 값이 전체 값에 영항을 주기 때문.

따라서 앞에서 부터 비용을 확인하면서 

만약 현재 값이 minCost이거나 minCost보다 크다면

-> 거리를 누적시킨다.

현재 값이 minCost보다 작다면

->  (어차피 지금 등장한 작은값은 앞에 누적거리에 영향을 못미침) 이전 누적거리까지의 기름값을 계산해준다. 

minCost가 업데이트 되고 누적거리도 초기화된다. 

 

비용 입력받는 부분을 따로 표시했지만 입력을 받으면서 동시에 함수를 진행하면 더 시간을 단축시킬 수 있다. 

#include <stdio.h>
#define MAX 100001
#define ll long long

using namespace std;
ll cost[MAX];
ll len[MAX];
int n;
int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++)
  {
    scanf("%lld", &len[i]);
  }

  for (int i = 0; i < n; i++)
  {
    scanf("%lld", &cost[i]);
  }

  ll minCost = cost[0], sum = 0, accLen = 0;
  for (int i = 0; i < n - 1; i++)
  {
    if (cost[i] >= minCost)
    {
      accLen += len[i];
    }
    else
    {
      sum += minCost * accLen;
      minCost = cost[i];
      accLen = len[i];
    }
  }

  sum += minCost * accLen;

  printf("%lld\n", sum);

  return 0;
}