[백준] 1680 - 쓰레기 수거

1. 문제

1680번: 쓰레기 수거

2. 개요

쓰레기장에서 출발한 쓰레기차가 여러 지점을 방문하며 쓰레기를 수거하고 있다.

차는 다음과 같은 상황에 쓰레기장으로 돌아가 쓰레기를 비운다.

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

모든 지점의 쓰레기를 수거하여 버려야 작업이 종료된다.

쓰레기차는 지역 내의 쓰레기를 분할하여 쓰레기차에 실을 수 없다.

쓰레기차의 용량과 지역의 수, 각 지역의 거리와 쓰레기가 주어졌을 때, 쓰레기차의 이동 거리를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 쓰레기차를 순서대로 각 지역에 이동시킨 후 현재 쓰레기차의 용량 + 해당 지역의 쓰레기의 양을 구한다.

만약 이 합이 쓰레기차의 용량 미만이라면 해당 지역의 쓰레기를 모두 싣고 다음 지역으로 이동한다.

만약 이 합이 쓰레기차의 용량과 같다면 해당 쓰레기를 모두 싣고 쓰레기장으로 돌아가 쓰레기를 모두 비운 후, 그 다음 지역으로 이동한다.

만약 이 합이 쓰레기차의 용량을 초과한다면 해당 지역의 쓰레기는 일단 그대로 두고 쓰레기장으로 돌아가 쓰레기를 모두 비운 후, 다시 해당 지역으로 이동한다.

이를 모든 지역에 대해 진행한다.

모든 지역에 대해 진행했음에도, 마지막 지역의 쓰레기를 실었을 때, 쓰레기차의 용량을 다 채우지 못했다면 쓰레기차는 돌아와 있지 않은 상황이 된다. 따라서 마지막으로 쓰레기차를 시작 지점으로 돌아오게 하는 작업까지 진행한다.

이후 지금까지 구한 쓰레기차의 총 이동 거리를 출력한다.

3-2. Python

import sys
from collections import deque

T = int(sys.stdin.readline())

for t in range(T):
    W, N = map(int, sys.stdin.readline().split())

    truckcap = 0
    movedistance = 0
    nowX = 0
    areas = deque()

    for i in range(N):
        areas.append(list(map(int, sys.stdin.readline().split())))

    while areas:
        nowX = areas[0][0]

        if areas[0][1] + truckcap < W:
            nowX, truckcap = areas[0][0], truckcap + areas[0][1]
            areas.popleft()

        elif areas[0][1] + truckcap == W:
            movedistance += nowX * 2
            nowX = 0
            truckcap = 0
            areas.popleft()

        else:
            movedistance += nowX * 2
            nowX = 0
            truckcap = 0

    movedistance += nowX * 2

    print(movedistance)

3-3. C#

namespace boj_1680
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new(Console.OpenStandardInput());
            StreamWriter sw = new(Console.OpenStandardOutput());

            int T = int.Parse(sr.ReadLine());

            for (int t = 0; t < T; t++)
            {
                string[] input = sr.ReadLine().Split();
                int W = int.Parse(input[0]);
                int N = int.Parse(input[1]);

                int truckcap = 0;
                int movedistance = 0;
                int nowX = 0;
                Queue<int[]> areas = new();

                for (int i = 0; i < N; i++)
                {
                    areas.Enqueue(Array.ConvertAll(sr.ReadLine().Split(), int.Parse));
                }

                while (areas.Count > 0)
                {
                    nowX = areas.Peek()[0];

                    if (areas.Peek()[1] + truckcap < W)
                    {
                        nowX = areas.Peek()[0];
                        truckcap += areas.Peek()[1];
                        areas.Dequeue();
                    }

                    else if (areas.Peek()[1] + truckcap == W)
                    {
                        movedistance += nowX * 2;
                        nowX = 0;
                        truckcap = 0;
                        areas.Dequeue();
                    }

                    else
                    {
                        movedistance += nowX * 2;
                        nowX = 0;
                        truckcap = 0;
                    }
                }

                movedistance += nowX * 2;

                sw.WriteLine(movedistance);
            }

            sw.Close();
        }
    }
}