[백준] 1680: 쓰레기 수거

문제 링크

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

접근 방식 / 풀이

입력에서부터 지점의 거리 기준으로 오름차순인 값이 주어졌기 때문에, 크게 정렬을 할 필요 없이 순조롭게 문제를 풀 수 있었다.

쓰레기차의 행동의 기준은 다음과 같다.

1. 가까운 지점부터 방문한다.
2. 쓰레기의 양이 최대 용량과 같을 때, 시작 지점에 가서 쓰레기를 비우고 온다.
3. 쓰레기를 넣을 수 없을 때, 시작 지점에 가서 쓰레기를 비우고 온 뒤 수거한다.

따라서 입력받은 값을 순차적으로 순회하면서, 용량과 이동 거리를 더해준다.

그 과정에서 현재 용량이 쓰레기차의 용량보다 크다면, (현재 위치 - 시작 지점(0)) * 2만큼 이동한 뒤 현재 용량을 해당 지점의 쓰레기 양으로 바꿔준다.
만약 현재 용량이 쓰레기차의 용량과 같고, 이 위치가 마지막 지점이 아니라면 (현재 위치 - 시작 지점(0)) * 2만큼 이동하고, 현재 용량을 0으로 바꿔준다.

이렇게 순회하면서 제일 마지막에 있는 지점에서 for문은 끝나게 되고, 이 상태에서의 최종 거리에 (현재 위치 - 시작 지점)을 더해주며 답을 도출한다.

답안 코드 링크 (Github)

Github Solution Link

정답 코드

#include <iostream>
#include <vector>
#define fastio                      \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL)
using namespace std;

int main(void)
{
	vector<pair<int, int>> lst;
	int t_case, truck_size, trash_num, dist, trash, cur_size, cur_dist, tot_dist;

    fastio;
	cin >> t_case;
	while (t_case--)
	{
		cin >> truck_size >> trash_num;
		lst.clear();
		for (int i = 0; i < trash_num; i++)
		{
			cin >> dist >> trash;
			lst.push_back({dist, trash});
		}
		tot_dist = 0;
		cur_dist = 0;
		cur_size = 0;
		for (int i = 0; i < trash_num; i++)
		{
			tot_dist += lst[i].first - cur_dist;
			cur_dist = lst[i].first;
			cur_size += lst[i].second;
			if (cur_size > truck_size)
			{
				tot_dist += lst[i].first * 2;
				cur_size = lst[i].second;
			}
			else if (cur_size == truck_size && i != trash_num - 1)
			{
				tot_dist += lst[i].first * 2;
				cur_size = 0;
			}
		}
		cout << tot_dist + lst[trash_num - 1].first << "\n";
	}
	return (0);
}