주유소

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

문제 풀이 과정

예제 풀이

위 예제를 기반으로 총 3가지의 접근 방식을 제작했다. (각 주유소의 위치를 노드라고 표현한다.)

1. Node1에서 기름을 전부 다 넣는 경우

6 * 5 = 30
총 30원

2. 다음 Node까지의 거리만 주유하는 방식

Node1 => 2 5 =10
Node2 => 3 2 = 6
Node3 => 4 * 1= 4
총 20원

3. 현재 노드와 다음 노드의 주유소의 기름값을 비교하여 판단하는 방식

Node1과 Node2 비교: 5>2이므로 현재 위치에서는 다음 Node까지의 이동거리만큼만 주유
Node2와 Node3 비교: 2<4이므로 Node3까지만의 거리가 아닌 Node4를 비교해야함
Node2와 Node4 비교: 2>1이지만, 마지막 Node이므로 별도의 이동 필요 X

위 과정을 거쳐 (52) + (24) = 18로, 총 18원이라는 결과 도출

최종 로직

1. 현재 Node와 다음 Node간의 기름값 비교

2-1. 현재 Node의 기름값이 비쌀 경우, 측정된 총 거리 * 현재 주유소의 기름값을 결과값에 더함

2-2. 현재 Node의 기름값이 싸거나 같은 경우, 비교할 다음 Node를 그 다음 Node로 변경하며 측정 거리에 움직이는 거리를 더함

3. 위 1~2번 과정을 마지막 Node에 도달할 때까지 반복 수행

주의사항

• 시작 상태는 기름이 없으므로 무조건 첫 번째 노드에서는 기름을 넣어야 한다는 점
• 마지막 주유소의 기름값은 무의미하다는 점

놓친 사항

처음 위 방식으로 작성한 코드의 결과는 아래의 부분 점수(58점)를 받았다. 그 이유를 파악해보았더니 아래의 부분을 놓친 것을 알 수 있었다.

문제 입력 조건

• 도시 수 정수 N(2 ≤ N ≤ 100,000)
• 인접한 두 도시를 연결하는 도로의 길이 (1이상 1,000,000,000 이하의 자연수)
• 주유소의 리터당 가격 (1 이상 1,000,000,000)

위와 같은 문제 입력 조건에서, 결과값은 int의 범위를 초과할 수 있다고 판단하여, result변수를 long long 타입으로 선언하여 활용하였는데, 거리를 더하는 변수 또한 int 범위를 초과할 수 있다는 점을 간과했던 것이었다.
그렇기에, 움직인 거리를 계산할 때 활용하는 변수인 move_dist 또한 long long 타입으로 변경하여 100점을 받을 수 있었다.

부분 점수

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define MAX 100000 + 1
#define ll long long

int N;
int dist[MAX];
int gas[MAX];
ll solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(dist, 0, sizeof(dist));
    memset(gas, 0, sizeof(gas));

    cin >> N;
    for(int i = 1; i < N; i++) {
        cin >> dist[i];
    }
    for(int i = 1; i < N  + 1; i++) {
        cin >> gas[i];
    }

    cout << solve() << endl;

    return 0;
}

ll solve() {
    ll result = 0; // 결과 저장 값
    int now_idx = 1; // 현재 노드
    int comp_idx = 2; // 비교 노드

    // 비교 과정 진행
    int move_dist = 0;
    while(now_idx < N) {
        // 현재 노드의 주유비가 비쌀 경우
        if(gas[now_idx] > gas[comp_idx]) {
            move_dist += dist[comp_idx - 1];
            result += move_dist * gas[now_idx];
            now_idx = comp_idx;
            comp_idx++;
            
            // 움직인 거리 초기화 (계산 완료했으므로)
            move_dist = 0;
        }
        // 현재 노드의 주유비가 쌀 경우
        else {
            move_dist += dist[comp_idx - 1];
            comp_idx++;
        }

        // 비교 대상이 마지막 노드인 경우는 분리해서 처리
        if(comp_idx == N) {
            move_dist += dist[comp_idx - 1];
            result += move_dist * gas[now_idx];
            now_idx = comp_idx;
        }
    }

    return result;
}

정답 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define MAX 100000 + 1
#define ll long long

int N;
int dist[MAX];
int gas[MAX];
ll solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(dist, 0, sizeof(dist));
    memset(gas, 0, sizeof(gas));

    cin >> N;
    for(int i = 1; i < N; i++) {
        cin >> dist[i];
    }
    for(int i = 1; i < N  + 1; i++) {
        cin >> gas[i];
    }

    cout << solve() << endl;

    return 0;
}

ll solve() {
    ll result = 0; // 결과 저장 값
    int now_idx = 1; // 현재 노드
    int comp_idx = 2; // 비교 노드

    // 비교 과정 진행
    ll move_dist = 0;
    while(now_idx < N) {
        // 현재 노드의 주유비가 비쌀 경우
        if(gas[now_idx] > gas[comp_idx]) {
            move_dist += dist[comp_idx - 1];
            result += move_dist * gas[now_idx];
            now_idx = comp_idx;
            comp_idx++;
            
            // 움직인 거리 초기화 (계산 완료했으므로)
            move_dist = 0;
        }
        // 현재 노드의 주유비가 쌀 경우
        else {
            move_dist += dist[comp_idx - 1];
            comp_idx++;
        }

        // 비교 대상이 마지막 노드인 경우는 분리해서 처리
        if(comp_idx == N) {
            move_dist += dist[comp_idx - 1];
            result += move_dist * gas[now_idx];
            now_idx = comp_idx;
        }
    }

    return result;
}