백준 BOJ 13305 - 주유소

정올 문제라 한다.

생각을 살짝만 뒤집으면 아주 쉽게 풀수 있는 그리디 문제가 된다.

핵심은 "반드시 앞 도시에서 기름을 미리 쟁여둘 필요가 없다" 이다.

뒤의 모든 도시들을 보고 나중에 기름이 필요할거 같으니 사두는건 너무 복잡한 행위다.

그냥 뒤의 도시에 가보고

기름가격이 더 비싸면

지난 도시에서 기름을 사도 되는 것이다.

최첨단 이동장치가 있어서

기름이 배달이된다 생각하면 되려나 ㅋㅋㅋㅋ

 

아무튼 이렇게 문제를 보게 되면

문제는 단순히

가장 적은 기름값을 지니는 도시의 위치를 기억해뒀다가

그 위치의 기름을 계속 사들이기만 하면 되는

그리디 문제가 된다.

 

#include <stdio.h>

#define INF 1000000007

typedef long long int ll;

int road[123456] = {0};
int oil[123456]  = {0};

int min(int a, int b){return a>b?b:a;}

int main(){
	int oilvalue = INF;
	int n;
	ll ans = 0;
	
	scanf("%d", &n);
	for(int i=0; i<n-1; i++) scanf("%d", &road[i]);
	for(int i=0; i<n;   i++) scanf("%d", &oil[i]);
	
	for(int i=0; i<n-1; i++){
		oilvalue = min(oilvalue, oil[i]);
		ans += (ll)road[i] * (ll)oilvalue;
	}
	printf("%lld", ans);
	return 0;
}

oilvalue가 가장 싼 기름의 가격이다.

매 도시를 들릴때마다 기름을 갱신하고

그 앞에 지나야할 도로 분량의 기름을 산다.

 

깔끔하게 AC.