백준 알고리즘 13305(주유소) - python, c++

백준 알고리즘 13305(주유소) - python, c++

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

13305번: 주유소

도시에서 주유하는 리터당 가격(price)과 거리(distance)를 이용하여 최소 거리를 구하는 문제.

price는 도시의 수인 N 개의 배열, distance는 도시 간의 거리이기 때문에 N-1 개의 배열을 갖는다.

그리디 알고리즘으로 접근하여 해결하는 방법.

---

[문제 풀이]

1. 그리디의 기준은 price이고, 더 작은 price의 idx를 기억하면서 진행.

    - 차례대로 진행하면서 min 값을 구하는 순서로 생각하면 쉽다.

    - 그리디의 기준이 price인 이유는, 싼 가격으로 미리 주유하면 되기 때문!

가야할 곳의 price가 더 큰 경우를 만나면,

price가 작아지는 경우를 만날 때까지의 거리만큼 미리 주유하면 된다.

 

2. 위처럼 적용하여 price 값과 distance 값을 idx에 맞게 곱해주어 누적한다.

3. (c++) 모든 조건을 위해 큰 수를 커버하도록 long type을 취해준다.

 

[python]

import sys
N = int(sys.stdin.readline().rstrip())
dist = list(map(int, sys.stdin.readline().split()))  # distance
price = list(map(int, sys.stdin.readline().split()))  # price

result = 0
min_idx = 0
for i in range(N-1):
    # 더 작은 price의 idx를 기억
    if price[min_idx] >= price[i]:
        price[min_idx] = price[i]
        min_idx = i
    result += price[min_idx] * dist[i]

print(result)

 

[c++]

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N = 0;
	vector<long> dist, price;

	scanf("%d", &N);
	long n = 0;
	for (int i = 0; i < N-1; i++) {
		scanf("%d", &n);
		dist.push_back(n);
	}
	for (int i = 0; i < N; i++) {
		scanf("%d", &n);
		price.push_back(n);
	}
	
	long min_idx = 0, result = 0;
	for (int i = 0; i < N-1; i++) {
		// 더 작은 price의 idx를 기억
		if (price[min_idx] >= price[i]) {
			price[min_idx] = price[i];
			min_idx = i;
		}
		result += price[min_idx] * dist[i];
	}
	printf("%ld\n", result); // long int
	return 0;
}