[백준] 13305번 주유소

문제: 13305번: 주유소

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

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

    int n; // 도시의 개수
    cin >> n;

    vector<long long> nextDists;
    for (int i = 0; i < n - 1; i++) {
        long long dist;
        cin >> dist;
        nextDists.push_back(dist);
    }

    vector<long long> costs;
    for (int i = 0; i < n; i++) {
        long long cost;
        cin >> cost;
        costs.push_back(cost);
    }

    long long prev = costs[0];
    long long cur = -1;
    long long totalCost = costs[0] * nextDists[0]; // 맨 처음 지역에서 일단 필요한만큼 더해주기
    for (int i = 1; i < n - 1; i++) {
        cur = costs[i];

        if (prev < cur)
            totalCost += prev * nextDists[i];
        else {
            totalCost += cur * nextDists[i];
            prev = cur;
        }
    }
    cout << totalCost << "\n";


    return 0;
}

 

음.. 별로 어렵지 않았다. 문제 풀이의 핵심은 일단 최대한 적은 돈을 사용하도록 하는 것이다. 즉, 이를 위해서는 현재 지역과 이전 지역의 주유 비용 중 값이 덜 나가는 값으로 충전해주면 되는 것이다. 

 

현재 지역의 주유 비용이 더 작다면 그제서야 prev 값을 현재 지역의 주유 비용으로 업데이트 해주면 된다. 아 그런데 처음 문제 코드 제출했을때는 58점이 나왔는데 이유를 찾아보니까 또 크기 범위를 잘못 설정해줘서 그런 것이었다;; long long 으로 해줘야 하는데 int 로 하니까 값이 이상해져서...;; 문제 조건을 꼼꼼히 읽어야하는데 이게 잘 안된다..

 

 

참고자료:

[c++][Greedy] 백준 13305번 문제 풀이

[c++][Greedy] 백준 13305번 문제 풀이

백준 13305 주유소 (JAVA) : 네이버 블로그

백준 13305 주유소 (JAVA)

문제 풀고나서 다른 사람들 풀이도 한 번 봤는데 비슷하게 푼 것 같다.