[c++] 백준 13305: 주유소

[c++] 백준 13305: 주유소

🥈실버 3

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

13305번: 주유소

---

접근

원 안의 숫자가 리터 당 기름의 가격, 막대 위의 숫자가 다음 도시까지의 거리일 때, 맨 오른쪽 도시까지 가기 위한 최소 비용을 출력하는 문제.

 

5원짜리 도시에서는 다음 도시까지 필요한 거리만큼만 기름을 사는 것이 합리적이다. 다음 도시에서는 리터 당 기름의 가격이 2원밖에 하지 않기 때문이다. > 5 * 2 = 10

 

만약 2원짜리 도시에서 다음 도시까지 필요한 거리 3만큼의 기름을 사면 2 * 3 = 6,

4원짜리 도시에서 다음 도시까지 필요한 거리 1만큼의 기름을 사면 4 * 1 = 4,

따라서 합은 10이된다.

 

그러나 2원짜리 도시에서는 다음 도시까지 필요한 거리보다 더 많은 기름을 사는 것이 합리적이다. 

왜냐하면 그 다음 도시는 리터당 4원을 주고 구매해야하기 때문에 차라리 2원짜리 도시에서 더 많은 기름을 구매해서 출발하는게 비용을 줄일 수 있기 때문이다.

 

현재 도시의 가격과 다음 도시의 가격을 비교했을 때 더 저렴한 도시의 가격을 minPrice라고 한다면, 매 턴마다 (minPrice * 다음 도로의 거리)를 전체 비용에 더해주도록 하면 된다.

 

문제에 다음과 같은 조건이 주어져 있다.

표준 입력으로 다음 정보가 주어진다.
첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다.
다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다.
다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다.
제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

도시마다의 기름 값은 N개의 배열로 잡고 도로의 길이는 N-1개의 배열로 잡아야 한다.

그리고 각 도시의 기름값에 대한 배열과 도로의 길이에 대한 배열, 정답으로 출력할 값은 long long으로 선언해야 한다.

출력될 값은 minPrice * 다음 도로의 길이의 합으로 되어있기 때문이다.

 

   

여기 조건에서 리터 당 가격은 최대 10000이라고 해서 처음 최소값을 10001로 잡고 진행했는데 자꾸 틀렸다고 나온다.

그냥 입력받은 각 도시의 가격 배열의 첫번째 값으로 설정하니까 정답으로 처리가 되었다...

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll cityNum;	// 입력받을 도시의 수
  cin >> cityNum;
  ll loadLength[cityNum-1];	// 입력받을 도로들의 값
  ll cityPrice[cityNum];	// 입력받을 도시마다의 기름 값
  for (ll i = 0; i < cityNum-1; i++) {
    cin >> loadLength[i];
  }
  
  for (ll i = 0; i < cityNum; i++) {
    cin >> cityPrice[i];
  }
  ll minPrice = cityPrice[0];	// 10001같은 걸로 하니까 틀렸다고 나와서 그냥 첫번째 값으로 했다.

  ll ans = 0;
  for (ll i = 0; i < cityNum-1; i++) {
    minPrice = min(minPrice, cityPrice[i]);	// 기존 값과 다음 도시 중 더 싼 값을 기준으로 한다.
    ans += minPrice * loadLength[i];	// 이렇게 할 경우 도로에 대해서는 다음 인덱스로 이동하는 반면, 더 싼 값의 도시에 대해서 계산을 진행할 수 있다.
  }
  cout << ans;

  return 0;
}