안녕하세요! 오늘은 백준 알고리즘 문제 중 Silver III 난이도의 "주유소" 문제를 풀어보겠습니다. 이 문제는 C++ 언어를 사용하여 해결했으며, 그리디(Greedy) 알고리즘을 통해 효율적으로 접근할 수 있습니다.

백준 13305: 주유소

안녕하세요! 오늘은 백준 알고리즘 문제 중 Silver III 난이도의 "주유소" 문제를 풀어보겠습니다. 이 문제는 C++ 언어를 사용하여 해결했으며, 그리디(Greedy) 알고리즘을 통해 효율적으로 접근할 수 있습니다.

문제 번호: 13305
문제명: 주유소
난이도: Silver III
사용 언어: C++
실행 시간: 84 ms
메모리: 3588 KB

문제 소개

도시 N개가 일렬로 늘어서 있고, 각 도시 사이의 거리가 주어집니다. 각 도시에서는 특정 가격으로 기름을 판매합니다. 우리는 첫 번째 도시에서 출발하여 마지막 도시까지 이동해야 하며, 이동하는 동안 필요한 만큼의 기름을 구매해야 합니다. 기름통의 크기는 무제한이며, 우리는 최소한의 비용으로 마지막 도시까지 도착하는 것이 목표입니다.

가장 중요한 제약 조건은 기름 가격이 오르락내리락 한다는 것입니다. 현재 도시보다 기름 가격이 싼 도시가 있다면, 그 도시에서 필요한 만큼의 기름을 미리 사두는 것이 유리할 수 있습니다.

접근 방법

이 문제는 "최소 비용으로 목표 지점에 도달하라"는 점에서 그리디 알고리즘을 적용하기에 적합해 보입니다. 각 도시에서 기름을 구매할 때, 현재 시점에서 미래의 모든 도시 중 가장 저렴한 가격을 파악하고, 해당 가격을 기준으로 기름을 구매하면 전체 비용을 최소화할 수 있을 것이라는 아이디어를 얻을 수 있습니다.

핵심 아이디어:
현재 도시에서 다음 도시까지 이동하는 데 필요한 기름은, 지금까지 거쳐온 도시들 중 가장 저렴한 가격의 주유소에서 구매한 기름으로 충당한다고 가정합니다.

왜냐하면, 만약 현재 도시보다 더 싼 가격의 주유소가 미래에 있다면, 우리는 그 싼 주유소에 도착해서 기름을 구매하는 것이 당연히 이득입니다. 따라서 현재 도시에서 기름을 구매해야 한다면, 그것은 앞으로 만나는 모든 도시들의 기름 가격이 현재 도시보다 비싸거나 같을 때만 고려할 가치가 있습니다. 하지만 그리디하게 생각하면, 현재 도시를 포함하여 지금까지 거쳐온 도시들 중 가장 싼 가격을 가진 도시의 기름을 이용하면 됩니다.

사용 알고리즘/자료구조:

그리디 알고리즘: 현재 상황에서 가장 최적의 선택을 하여 전체 최적해를 찾는 방식입니다.
std::vector: 각 도시 사이의 거리와 기름 가격을 저장하기 위해 사용했습니다.
long long: 총 비용이 매우 커질 수 있으므로, 오버플로우를 방지하기 위해 long long 타입을 사용했습니다.

풀이 과정

입력 받기:
- 도시의 개수 N을 입력받습니다.
- N-1개의 도시 사이의 거리를 d 벡터에 저장합니다. d[i]는 i번째 도시와 i+1번째 도시 사이의 거리입니다.
- N개의 도시 각각의 기름 가격을 p 벡터에 저장합니다. p[i]는 i번째 도시의 기름 가격입니다.
최소 가격 추적:
- minPrice 변수를 선언하고, 첫 번째 도시의 기름 가격 p[0]으로 초기화합니다. 이 변수는 지금까지 방문한 도시들(1부터 현재 위치까지) 중 가장 싼 기름 가격을 추적하는 역할을 합니다.
총 비용 계산:
- ans 변수를 0으로 초기화하여 총 비용을 저장할 준비를 합니다.
- i를 0부터 N-2까지 반복합니다 (즉, 0번째 도시부터 N-2번째 도시까지). 각 반복은 i번째 도시에서 i+1번째 도시로 이동하는 구간을 나타냅니다.
- 핵심 로직:
  - minPrice = min(minPrice, p[i]);
    이 줄이 그리디의 핵심입니다. i번째 도시의 기름 가격 p[i]를 현재까지의 최소 가격 minPrice와 비교하여 더 작은 값으로 minPrice를 갱신합니다. 이렇게 하면 i+1번째 도시로 이동하는 데 필요한 기름은 항상 1번 도시부터 i번 도시까지 중 가장 싼 가격으로 구매한 것으로 간주하게 됩니다.
  - ans += minPrice * d[i];
    i번째 도시와 i+1번째 도시 사이의 거리 d[i]만큼 이동하는 데 필요한 기름 비용을 계산합니다. 이 비용은 minPrice (즉, 1번부터 i번 도시까지의 최소 기름 가격)와 거리 d[i]를 곱한 값입니다. 이 값을 ans에 더해줍니다.
결과 출력:
- 모든 구간의 기름 비용이 계산되면, 최종 ans 값을 출력합니다.

주의할 점:

N개의 도시가 있고 N-1개의 거리가 주어지므로, 인덱스 관리에 주의해야 합니다. d 벡터는 N-1개의 요소를, p 벡터는 N개의 요소를 가집니다.
총 비용이 매우 클 수 있으므로 long long 타입을 사용하여 오버플로우를 방지해야 합니다.

코드 설명

#include <bits/stdc++.h> // 필요한 모든 헤더를 포함하는 편리한 방법
using namespace std;      // std 네임스페이스 사용

int main() {
    // 실행 속도 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // d: 각 도시 사이의 거리 (N-1개의 원소)
    // d[i]는 i번째 도시와 i+1번째 도시 사이의 거리
    vector<long long> d(N-1);
    for (int i = 0; i < N-1; i++) cin >> d[i];

    // p: 각 도시의 기름 가격 (N개의 원소)
    // p[i]는 i번째 도시의 기름 가격
    vector<long long> p(N);
    for (int i = 0; i < N; i++) cin >> p[i];

    long long ans = 0; // 총 비용을 저장할 변수 (long long으로 선언)
    
    // minPrice: 지금까지 방문한 도시 중 가장 싼 주유소 가격을 추적
    // 처음에는 첫 번째 도시의 가격으로 초기화
    long long minPrice = p[0]; 

    // 0번째 도시부터 N-2번째 도시까지 반복
    // i는 현재 도시를 의미하며, i+1번째 도시로 이동하는 구간을 처리
    for (int i = 0; i < N-1; i++) {
        // 현재 도시(i)의 기름 가격을 지금까지의 최소 가격(minPrice)과 비교하여 갱신
        // 이렇게 하면 i+1번째 도시로 가는 기름은 1..i 도시 중 가장 싼 곳에서 샀다고 간주
        minPrice = min(minPrice, p[i]);

        // (i -> i+1) 구간 d[i]를 지나는 데 드는 비용을 계산
        // 비용 = (1..i 중 최저가) * d[i]
        ans += minPrice * d[i];
    }
    
    // 최종 계산된 최소 총 비용 출력
    cout << ans;

    return 0; // 프로그램 종료
}

주요 부분 설명

vector<long long> d(N-1), p(N);: 각 도시 사이의 거리와 도시별 기름 가격을 저장하기 위한 long long 타입의 벡터입니다.
long long ans = 0;: 최종적으로 계산될 총 이동 비용을 저장할 변수입니다.
long long minPrice = p[0];: 현재까지 방문한 도시들 중 가장 저렴한 기름 가격을 저장합니다. 첫 번째 도시에서 출발하므로, p[0]으로 초기화합니다.
for (int i = 0; i < N-1; i++): 0번 도시부터 N-2번 도시까지 순회하며 각 구간(i에서 i+1로 이동)의 비용을 계산합니다.
minPrice = min(minPrice, p[i]);: 이것이 그리디의 핵심입니다. 현재 도시 i의 가격 p[i]와 이전에 기록된 minPrice를 비교하여 더 작은 값으로 minPrice를 갱신합니다. 즉, i+1로 갈 때 사용할 기름은 0번부터 i번 도시까지 중에 가장 싼 가격으로 구매한 것으로 간주하는 것입니다.
ans += minPrice * d[i];: i번 도시와 i+1번 도시 사이의 거리 d[i]만큼 이동하는 데 필요한 기름 비용을 minPrice를 이용해 계산하고 ans에 더합니다.

복잡도 분석

시간 복잡도:
- 입력을 받는 데 O(N) 시간이 소요됩니다.
- for 루프는 N-1번 반복됩니다. 루프 안의 연산(min, 곱셈, 덧셈)은 모두 상수 시간 O(1)이므로, 총 O(N) 시간이 소요됩니다.
- 따라서 전체 시간 복잡도는 O(N) 입니다.
공간 복잡도:
- d 벡터는 N-1개의 long long 값을 저장하고, p 벡터는 N개의 long long 값을 저장합니다.
- 따라서 총 O(N)의 공간이 사용됩니다.
- 전체 공간 복잡도는 O(N) 입니다.

배운 점

이 "주유소" 문제를 풀면서 몇 가지 중요한 점을 배울 수 있었습니다.

그리디 알고리즘의 힘: 복잡해 보이는 문제도 현재 상황에서 가장 합리적인 선택을 반복함으로써 전체 최적해를 찾을 수 있다는 것을 다시 한번 확인할 수 있었습니다. 특히, 미래의 모든 정보를 고려하는 것이 아니라 "지금까지의 최적 상태"를 유지하는 것이 중요하다는 것을 깨달았습니다.
long long의 중요성: 알고리즘 문제에서는 입력 값의 범위나 계산 결과가 예상보다 커질 수 있습니다. 이 문제처럼 비용이 누적되는 경우, int 범위를 넘어가는 long long 타입을 사용하지 않으면 오버플로우로 인해 잘못된 결과를 얻게 됩니다.
구간별 처리 및 누적 합: 각 구간(i에서 i+1까지)의 비용을 계산하고 이를 누적하여 전체 비용을 구하는 방식은 다양한 문제에서 활용될 수 있는 패턴입니다.
인덱스 관리: N개의 도시와 N-1개의 거리를 다룰 때, 인덱스가 0부터 시작하는 것을 고려하여 정확하게 벡터에 접근하는 것이 중요합니다.

이 문제는 그리디 알고리즘을 연습하기에 아주 좋은 문제이며, 실제 프로그래밍 대회에서도 비슷한 유형의 문제가 자주 출제됩니다. 앞으로도 다양한 문제를 풀면서 알고리즘적 사고력을 키워나가겠습니다!