[ 백준 13305] 주유소(C++)

13305번: 주유소

문제!

---

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

 

---

요약하면 최 왼쪽에서 오른쪽 끝으로 이동을 하게하는 최소의 비용을 구하는 문제입니다.

 

각 도시의 기름값이 다 다르고 , 도시간의 거리가 다 다른 상태에서 어떻게 풀어야 할지를 생각해 보았는데

 

 

<끄적인것들..>

// 남은 거리 만큼의 기름이 필요 

// 그러면 뒤에서 부터 출발 할때 
// 그안에서 기름이 딱 맞아야지
// 뒤에서 거리를 더해주면서?

// 앞에서 탐색하면?  일단 처음에 넣을 기름을 선택해야되는데

// 그러면 정렬을 시킨다?  모든 부분을 보기엔 좀 
// 다음 정류장까지의 거리와  현재 기름비용?


//일단 다음 정류장까지의 비용을 넣고 계속해서 비용을 비교해주면서 적게 나오면 교체 해서 계속 반복? -- 이거네

대충 요약하면 

1. 끝에서 부터 보기

2. 일일히 넣어보기

3. 1정류장씩 이동하면서 기름값 * 거리를 계속 더해주기

 

이런식의 방법을 생각 해보았는데

이 중 3번째가 가장 빠르고 정확한 방법인것 같네요!

 

3번째 방법에 대해서 설명을 하자면

만약 1~2 까지 이동을 할때 일단 1번에서 기름을 구매해야합니다.

그리고 2~3 까지 이동을 할때

 

1번에서의 기름이 2번에서의 기름보다 싸다면? >>> 1번에서 넣어 온것처럼 1번기름 * 2~3번거리 를 더해주고

2번에서의 기름이 1번에서의 기름보다 싸다면? >>> 기름의 가격을 2번기름으로 최신화 해주고 2번기름 *2~3번거리 를 더해줍시다.

 

이걸 반복해주면? 끝!

 

 

 

그럼 바로 시작!

---

 

우선 거리와 비용을 저장해두고

int way[100001] = { 0 };// 거리
int cost[100001] = { 0 }; // 비용
long long answer = 0;

//~~~

cin >> N;
	for (int i = 1; i < N; i++) {// i~i+1 까지 거리
		cin >> way[i];
	}

	for (int i = 1; i < N+1; i++) {// i의 주유 비용
		cin >> cost[i];
	}

 

 

이 부분에서 기름의 값을 최신화 해주고 그만큼 이동시키며 끝까지 반복해주는 부분!

 

now_cost = cost[1]; // 일단 첫번째꺼 넣어주고
	answer += way[1]* now_cost;

	for (int i = 2; i < N+1; i++) {// 탐색을 나설것
		if (now_cost > cost[i]) {
			now_cost = cost[i];
		}
		answer += now_cost * way[i];
	}

	cout << answer;

 

 

코드로 짜니까 금방이네요 생각보다 방법이 빨리생각나서 금방 풀수있었습니다!

 

 

 

ALL

#include <iostream>

using namespace std;

int way[100001] = { 0 };// 거리
int cost[100001] = { 0 }; // 비용
long long answer = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	long long now_cost = 0;
	
	cin >> N;
	for (int i = 1; i < N; i++) {// i~i+1 까지 거리
		cin >> way[i];
	}

	for (int i = 1; i < N+1; i++) {// i의 주유 비용
		cin >> cost[i];
	}


	now_cost = cost[1]; // 일단 첫번째꺼 넣어주고
	answer += way[1]* now_cost;

	for (int i = 2; i < N+1; i++) {// 탐색을 나설것
		if (now_cost > cost[i]) {
			now_cost = cost[i];
		}
		answer += now_cost * way[i];
	}

	cout << answer;


	return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!