BOJ 13335. 트럭

🙇‍♀️[Silver I] 트럭 - 13335

문제 링크

성능 요약

메모리: 2024 KB, 시간: 0 ms

분류

자료 구조, 구현, 큐, 시뮬레이션

제출 일자

2024년 2월 1일 12:00:47

문제 설명

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a₁, a₂, ⋯ , a_n (1 ≤ a_i ≤ 10)가 주어지는데, a_i는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

🚀풀이

트럭들은 들어온 순서대로 이동해야한다.
그래서 트럭들은 queue를 이용했다.

다리의 상태가 중요하다.
현재 다리에 있는 트럭들의 무게와 다음에 들어올 트럭의 무게, 다리를 나가는 트럭의 무게가 중요하다.
다리의 상태를 확인하기 위한 배열을 만들었다.

int n, w, L;
// n : 트럭의 수
// w : 다리의 길이
// L : 최대 하중
vector<int> bridge;

// n = 1000, w = 100, L = 1000
// 시간 복잡도를 신경안써도 될정도
// 그럼 매 순간 다리위 무게를 계산해서 움직이기?

수의 양이 적어서 시간 복잡도를 계산안해도 되겠다는 판단이 들었다.

그래서 매 순간마다 다리의 무게를 계산하는 방식을 사용했다.
(지금 생각하니 양끝점만 빼고 더하는 방식도 나쁘지 않을듯)

입력을 받아주기 위한 세팅

cin >> n >> w >> L;
bridge = vector<int>(w); // 다리 길이 설정
queue<int> trucks;
int temp;
for (int i = 0; i < n; ++i)
{
	cin >> temp;
	trucks.push(temp);
}

int res = 0;

트럭들을 담은 큐가 빌 때까지 반복하다가 다리에 남아 있는 트럭들까지 모두 이동시키고 출력할 것이다.

// 큐가 빌 때 동안
while (trucks.empty() == false)
{
	// 다리 위 트럭 무게 확인
	int sum = 0;
	for (int i = 0; i < w; ++i)
	{
		sum += bridge[i];
	}

    // 다리 위 트럭과 들어올 트럭의 무게를 더하고 바로 나갈 수 있는 트럭의 무게를 뺸다.
	int temp = sum + trucks.front() - bridge[w - 1];
	if (temp <= L)
	{
		// 이동하기
		for (int i = w - 1; i > 0; --i)
		{
			bridge[i] = bridge[i - 1];
		}
		bridge[0] = trucks.front();
		trucks.pop();

		res++;
	}
	else
	{
		// 이동하기
		for (int i = w - 1; i > 0; --i)
		{
			bridge[i] = bridge[i - 1];
		}
		bridge[0] = 0;

		res++;
	}
}

// 다리에 남은거 움직이기
for (int i = 0; i < w; ++i)
{
	if (bridge[i] != 0)
	{
		temp = i;
		break;
	}
}
res += (w - temp);

// 결과 출력
cout << res;

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, w, L;
// n : 트럭의 수
// w : 다리의 길이
// L : 최대 하중
vector<int> bridge;

// n = 1000, w = 100, L = 1000
// 시간 복잡도를 신경안써도 될정도
// 그럼 매 순간 다리위 무게를 계산해서 움직이기?

void solve()
{
	cin >> n >> w >> L;
	bridge = vector<int>(w); // 다리 길이 설정
	queue<int> trucks;
	int temp;
	for (int i = 0; i < n; ++i)
	{
		cin >> temp;
		trucks.push(temp);
	}

	int res = 0;

	// 큐가 빌 때 동안
	while (trucks.empty() == false)
	{
		// 다리 위 트럭 무게 확인
		int sum = 0;
		for (int i = 0; i < w; ++i)
		{
			sum += bridge[i];
		}

		int temp = sum + trucks.front() - bridge[w - 1];
		if (temp <= L)
		{
			// 이동하기
			for (int i = w - 1; i > 0; --i)
			{
				bridge[i] = bridge[i - 1];
			}

			bridge[0] = trucks.front();
			trucks.pop();

			res++;
		}
		else
		{
			// 이동하기
			for (int i = w - 1; i > 0; --i)
			{
				bridge[i] = bridge[i - 1];
			}
			bridge[0] = 0;

			res++;
		}
	}

	// 다리에 남은거 움직이기
	for (int i = 0; i < w; ++i)
	{
		if (bridge[i] != 0)
		{
			temp = i;
			break;
		}
	}
	res += (w - temp);

	// 결과 출력
	cout << res;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}