백준 13305 주유소

www.acmicpc.net/problem/13305

13305번: 주유소

그리디 문제다 언제나 그렇듯 O(N)을 반복하며 각 순간의 최적의 선택을 해주어야한다. 이 문제의 경우 조건이 두가지가 존재한다. 하나는 오른쪽 도시로 가는데 최적의 비용이고 거리의 길이만큼 무조건의 기름을 갖고있어야했다. 

 

이 문제를 해결하기 위해서는 기준점이 되는 점의 기름 가격보다 더 적거나 같은 값의 가격이 나올 때 까지 반복문을 돌려 체크해준다. 

더 큰 점의 경우에는 지나가며 거리를 저장해준다. 더 작은 가격의 점을 만날 때 기준점의 가격과 거리를 곱해서 가격을 더해주면 된다. 

 

그리고 정점이 아래와 같은 경우 더해질일이 없다. 마지막에 값이 비워져있지 않다면 추가로 더해주어서 마무리를한다. 

 

1 2 3 4 5 6

항상 정점의 기름값이 커지기 때문에 더해질일이 없다. 

 

이 문제 또한 간단한 그림으로 설명해보겠다. 

 

1단계

1단계의 경우 기준이되는 5보다 작은 2를 바로 만나기 때문에 5와 거리 2를 곱해주어서 result에 저장해준다. 

2단계의 경우 기준이 되는 2보다 작은 포인트를 1에서 만나게된다. 그 사이에 있는 3과 1은 계속 저장해주고 1을 만났을 때 중간에 저장된 거리 x 기름 값 2를 곱해서 result에 더해주면 된다. 

 

따라서 답은 18이된다. 

 

#include <cstdio>
#define ll long long

ll distance[100002], point[100002];

int main(){
	int N;
	scanf("%d", &N);

	for(int i = 0; i < N-1; i++)
		scanf("%lld", &distance[i]);

	for(int i = 0; i < N; i++)
		scanf("%lld", &point[i]);
	
	ll baseNumber = point[0];
	ll subDistance = distance[0];
	ll result = 0;

	for(int i = 1; i < N; i++){
		if(point[i] <= baseNumber){
			result += baseNumber * subDistance;
			baseNumber = point[i];
			subDistance = distance[i];
		}else{
			subDistance+=distance[i];
		}
	}

	if(subDistance != 0){
		result+= baseNumber * subDistance;
	}

	printf("%lld", result);
}