[ 백준 ] 13305 / 주유소

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
36/228
post-thumbnail

# Appreciation

/*
 * Problem :: 13305 / 주유소
 *
 * Kind :: Greedy
 *
 * Insight
 * - 새로운 주유소에 도착할 때마다
 *   지나온 주유소(현재 도착한 주요소 포함)들 중의
 *   제일 싼 기름값을 알아야 한다
 *   + 그 값에 다음 주유소까지의 거리를 곱하면
 *     다음 주유소까지 가는데 최소 비용을 알 수 있다
 *     # 지금까지 만난 주유소들의 기름값들의 최소를 기억하는 변수를 선언하고
 *       새로운 주유소에 도착할 때마다 갱신해주자
 *
 * Point
 * - max(거리)=10^9, max(가격)=10^9
 *   max(비용)=10^18 이므로
 *   long 자료형을 사용해주자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
#define INF (1000000000+1)

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int D[N-1]; /* 주유소간 거리 */
    for (int i=0; i<N-1; i++)
        cin >> D[i];
    int P[N]; /* 주유소의 리터당 가격 */
    for (int i=0; i<N; i++)
        cin >> P[i];

    // Process
    long ans = 0;
    int mn = INF; /* 지금까지 만난 주유소들 중 제일 싼 기름값 */
    for (int i=0; i<N-1; i++) {
        mn = min(mn, P[i]);
        ans += (long)mn * D[i];
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글