[C++] 백준 13305번 : 주유소

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

13305번: 주유소

---

 문제 풀이

값들을 입력받고 최솟값을 최신화해서 두 도시 사이의 거리와 최솟값을 곱해서 결과에 더해주면 된다.

여기서 최솟값임을 따지는 것이 그리디 알고리즘의 핵심이다!

 함수 Solution

i번째 값이 최솟값보다 작으면 최솟값을 최신화한다.

이후 최솟값과 i번째 거리와 곱해서 ans에 더한다.

 느낀 점

처음에 프로그래머답지 못하게 문제를 너무 1차원적으로 접근했다. 각 거리 값을 더한 변수를 만들고 최솟값을 따로 찾는 과정에, 최솟값보다 크면 i번째 거리와 i번째 가격을 곱해서 더하고 최솟값과 거리가 같으면 남은 모든 거리와 최솟값을 곱해서 더하는 불필요한 과정을 진행했다. 그리디 함수다운 풀이법을 실행하지 못해서 아쉬운 문제이다.

 코드

#include <iostream>

using namespace std;

int n;
long long distances[100001];
long long prices[100001];
long long my_min = 1000000001, ans = 0;

void solution() {
	for (int i = 0; i < n; i++) {
		if (prices[i] < my_min) my_min = prices[i];
		ans += my_min * distances[i];
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n - 1;i++) {
		cin >> distances[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> prices[i];
	}

	solution();
	cout << ans;
}