BOJ 1680 - 쓰레기 수거 링크
(2023.08.24 기준 S4)

문제

쓰레기가 있는 지점 N개의 쓰레기장으로부터의 거리가 각각 주어진다.
쓰레기차는 쓰레기장에서 가까운 지점부터 방문하여, 쓰레기를 모으다가

1. 쓰레기의 양이 용량에 도달했을 때.
2. 그 지점의 쓰레기를 실었을 때 쓰레기차의 용량을 넘게 될 때.
3. 더 이상 쓰레기를 실을 지점이 없을 때.

위 세 경우에 해당하면 쓰레기장으로 돌아가 싣고 있는 쓰레기를 비워야 한다.

모든 쓰레기를 수거하여 쓰레기장에 도달했을 때, 쓰레기차의 총 이동 거리 출력

알고리즘

단순 시뮬레이션

풀이

거리가 가까운 쓰레기부터 순서대로 입력이 주어지기 때문에, 주어진 순서대로 쓰레기 하나하나 살펴보면 된다.

쓰레기 지점까지 이동하고, 쓰레기를 담고, 최대 용량을 넘을 것 같으면 쓰레기장에 갔다와서 비워주고 다시 와서 그 지점의 쓰레기를 담고, 쓰레기 용량이 꽉 차면 쓰레기장으로 돌아가서 비우고, 모든 쓰레기를 다 수거하면 쓰레기장으로 복귀하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

vector<pii> garbage;

void solve(){
    int W, N; cin >> W >> N;
    garbage.clear();
    for (int i = 0, x_i, w_i; i < N; i++){
        cin >> x_i >> w_i;
        garbage.push_back({x_i, w_i});
    }

    int w = 0, x = 0, d = 0; // 현재 쓰레기 양, 현재 위치, 움직인 거리
    for (auto [x_i, w_i]: garbage){ // 가까운 쓰레기부터 차례대로 방문한다.
        d += x_i - x; // 현재 위치에서 쓰레기까지의 거리를 더한다.
        x = x_i; // 현재 위치는 쓰레기 위치가 된다.
        w += w_i; // 쓰레기를 싣는다.

        if (w > W){ // 그 지점의 쓰레기를 실었을 때 쓰레기차의 용량을 넘게 될 때.
            d += x_i * 2; // 쓰레기를 비우기 위해 쓰레기장에 갔다 와야 한다.
            w = w_i; // 쓰레기를 비우고 와서 그 지점의 쓰레기를 싣는다.
        }

        if (w == W){ // 쓰레기의 양이 용량에 도달했을 때.
            d += x_i; // 현재 위치에서 쓰레기장까지의 거리를 더한다.
            x = 0; // 현재 위치는 쓰레기장이 된다.
            w = 0; // 쓰레기를 비운다.
        }
    }

    // 더 이상 쓰레기를 실을 지점이 없을 때.
    d += x; // 현재 위치에서 쓰레기장으로 돌아간다.

    cout << d << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline

def solve():
    W, N = map(int, input().split())
    garbage = [tuple(map(int, input().split())) for _ in range(N)]

    w = x = d = 0 # 현재 쓰레기 양, 현재 위치, 움직인 거리
    for x_i, w_i in garbage: # 가까운 쓰레기부터 차례대로 방문한다.
        d += x_i - x # 현재 위치에서 쓰레기까지의 거리를 더한다.
        x = x_i # 현재 위치는 쓰레기 위치가 된다.
        w += w_i # 쓰레기를 싣는다.

        if w > W: # 그 지점의 쓰레기를 실었을 때 쓰레기차의 용량을 넘게 될 때.
            d += x_i * 2 # 쓰레기를 비우기 위해 쓰레기장에 갔다 와야 한다.
            w = w_i # 쓰레기를 비우고 와서 그 지점의 쓰레기를 싣는다.

        if w == W: # 쓰레기의 양이 용량에 도달했을 때.
            d += x_i # 현재 위치에서 쓰레기장까지의 거리를 더한다.
            x = 0 # 현재 위치는 쓰레기장이 된다.
            w = 0 # 쓰레기를 비운다.

    # 더 이상 쓰레기를 실을 지점이 없을 때.
    d += x # 현재 위치에서 쓰레기장으로 돌아간다.

    print(d)

for _ in range(int(input())):
    solve()