백준, BOJ, 13305번 C++ [CPP]

이 문제도 어렵진 않다.

어렵다면 왜 이렇게 해야하는지?

에 대한 의문에 대한 해답일 것이다.

 

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

 

---

 

시간도 넉넉하다. 메모리도 넉넉하다.

long long을 쓸 것 같다는 생각을 하자.

 

#맞는 풀이

#include<iostream>
#include<vector>

using namespace std;

int numOfCity;

long long dist[100001]; // 도시별 거리
long long cost = 0;
long long price[100001]; // 도시별 가격
vector<int> vec; // 탐색한 도시의 위치를 담을 벡터


int main() {
    cin >> numOfCity;
    for (int i = 1; i <= numOfCity - 1; i++) {
        cin >> dist[i];    // i번째는 i번에서 i+1까지 가는 거리.
    }
    for (int i = 1; i <= numOfCity; i++) {
        cin >> price[i]; // i번째는 i번째 도시에서의 가격.
    }

    //첫번째 도시를 기준으로 가격이 낮은 도시를 탐색 - 찾았으면 도시를 기준으로 탐색
    int m = price[1];
    //첫번째 도시 다음부터 탐색
    for (int i = 2; i <= numOfCity; i++) {
        if (m >= price[i]) { // equal을 빼면 도시가 모두 같은 값을 가지고 있을 때 에러남
            m = price[i]; // 최솟값 갱신
            vec.push_back(i); // 도시위치
        }
    }

    //그리고 마지막 도시가 선택되지 않았다면 넣어줘야함.
    if (vec.back() != numOfCity) {
        vec.push_back(numOfCity);
    }

    //즉, 해당 위치까지는 출발한 도시에서 기름을 넣어야함.
    //4가 낮은 가격을 가지고 있다면 1~4까지는 1에서 기름을 넣고 가야함.
    int start = 1;
    for (int a : vec) {
        //start에서 해당 도시까지 거리만큼 start에서 기름을 넣음
        for (int i = start; i < a; i++) {
            cost += price[start] * dist[i];
        }
        //start갱신
        start = a;
    }

    cout << cost << "\n";

}

 

여기서 짠 이유는 무엇이냐..??

 

그냥 우리가 일상적으로 생각하는 대로 짰다.

 

우리가 어디를 가고싶고 최대한 경제적으로 가려면

비싸더라도 여기보다 싼 곳 까지만 갈 수 있을만큼 기름을 넣고

그 싼 곳에서 나머지를 다 넣는다면.. 경제적일 것이다.

 

 

여기서 포인트는 3가지다.

1

모든 도시의 기름이 같다면 

현실에선 한곳에서 다 넣겠지만

프로그래밍을 할 땐..

도착할 때마다 넣을 것인지 안 넣을 것인지 판단해야하기 때문에

1,1,1,1과 같이 주어진 예에서도  들릴때마다 다음도시까지 갈 기름만 넣게 만들었다.

 

2.

마지막 도시가 vec에 들어가지 않을 수 있다.

왜냐면 마지막 도시가.. 가격이 무척 비쌀 수 있기 때문이다.

 

결국 마지막도시까지 가야하기 때문에

마지막 도시가 vec에 있는지 체크하고 없으면 넣어야 한다.

즉, 마지막 도시 전의 가장 싼 기름값을 가지고 있는 도시에서 마지막 도시까지 기름을 다 넣게 만들겠다는 말이다.

 

3.

또한 마지막으로 start를 갱신해줘야 해당 도시부터 다음 싼 도시까지 계산이 가능하다.