[백준(BOJ)] 13305번 : 주유소 - C++[CPP]

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

13305번: 주유소

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그리디 알고리즘

 

---

 

⊙ 문제 접근 과정

 

제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1 이상 1,000,000,000 이하의 자연수라 long long을 사용해주었다. 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

ll N;
ll result=0;
vector<ll> dis;
vector<ll> city;

int main() {
    cin >> N;

    for(auto i=0;i<N-1;i++) {
        int x;
        cin >>x;
        dis.push_back(x);
    }

    for(auto i=0;i<N;i++) {
        int x;
        cin >> x;
        city.push_back(x);
    }

    ll temp=city[0];

    for(int indx=0;indx<=N-1;indx++) {
        if(temp<=city[indx+1]) {
            result+=dis[indx]*temp;
        } else {
            result+=dis[indx]*temp;
            temp=city[indx+1];
        }
    }
    cout << result;
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

코드가 간단해보이지만 처음엔 길었다. 최적화를 3번 해줬다. (TMI)

 

좋아요는 로그인하지 않아도 누를 수 있습니다!