[백준BaekJoon]13305: 주유소/C++

문제

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

 

풀이

그리디 알고리즘으로, 현재 단계에서 취할 수 있는 가장 최선의 선택을 하는 방법으로 탐색을 진행하였다.

 

현재 있는 지점의 가격이 제일 쌀 경우, 해당 가격을 기준으로 하여 탐색을 진행한다. 

초기값은 첫번째 주유소의 가격으로 설정한다. 

2번째 주유소의 가격이 더 싸므로 price값을 2로 변경해주고, 3번째 주유소의 가격은 현재 price 값인 2보다 비싸므로 price 값을 유지한다. 

#include <bits/stdc++.h> 
using namespace std;

long long N;
long long W[100000], V[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	long long N, price, ans = 0;
	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		cin >> W[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> V[i];
	}

	price = V[0];

	for (int i = 0; i < N ; i++) {
		if (V[i] <= price) {
			price = V[i];
		}
		ans += price * W[i];
	}

	cout << ans;
}

 

초반에는 거리값과 현재 가격을 동시에 갱신하는 무모한 코드를 짰었다.

아직 해답을 한 번에 딱 떠올리려면 멀었구나...싶다.

근데 막상 또 풀어보고 나니 문제 난이도를 더 높여도 될 것 같다는 생각도 들긴 했다.

 

일단 지금까지 풀었던 문제들을 복습하며,, 비슷한 수준의 문제들까지 잘 풀어보려 한다 .. !