언어/c, c++

*(백준BAEKJOOB )* 13305 주유소

깡 딱 2023. 5. 2. 19:18
728x90

 

문제출처 : https://www.acmicpc.net/problem/13305
 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

 

 

문제풀이 :

 

 

코드

 

#include <iostream>

using namespace std;

int dist[100000];
int cost[100000];

int main(void){
    int n;
    long long total=0;
    long long c_now;
    
    scanf("%d", &n);
    
    for(int i=1; i<n; i++){
        scanf("%d", &dist[i]);
    }
    for(int i=0; i<n; i++){
        scanf("%d", &cost[i]);
    }
    c_now = cost[0];
    total = c_now * dist[1];
    //첫번째->두번째 이동
    
    for(int i=1; i<n; i++){
        if(c_now < cost[i]){
            total += c_now * dist[i+1];
        }
        else{
            c_now = cost[i];
            total += c_now*dist[i+1];
        }
    }
    printf("%lld\n", total);
}

 

 

 

 

 

참고:

그리디 알고리즘에 대한 기초와

거리비용 long long 이용하는거 

728x90