[백준] 트럭 13335번 C++ 풀이

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

13335번: 트럭

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 트럭의 수, 다리의 길이, 최대하중
int N, W, L;
int Time = 0;
int cL=0; // 현재 하중
vector<int> v;
queue<pair<int,int>> q;
void solve()
{
	int i = 0;
	while(1){

		if (i<N && cL + v[i] <= L)
		{
			q.push(make_pair(W, v[i]));
			cL += v[i];
			i++;
		}

		int s = q.size();

		for (int j = 0; j < s ; j++)
		{
			if (!q.empty())
			{
				int ctime = q.front().first;
				int weight = q.front().second;
				q.pop();

				if (ctime - 1 != 0)
					q.push(make_pair(ctime - 1, weight));
				else
					cL -= weight;

			}
		}

		Time++;

		if (i == N && q.empty())
			break;
	}

	cout << Time+1;
}

int main(void)
{
	cin >> N >> W >> L;
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		v.push_back(n);
	}

	solve();
}

 

변수

// 트럭의 수, 다리의 길이, 최대하중
int N, W, L;
int Time = 0;
int cL=0; // 현재 하중
vector<int> v;
queue<pair<int,int>> q;

v에 트럭의 무게들을 넣고

q에는 다리 위에 올라가 있는 트럭의 정보를 넣어줄 겁니다 < 남은 다리 길이, 트럭의 무게 >

cL : 현재 다리위의 트럭 무게 총합

 

main 함수

int main(void)
{
	cin >> N >> W >> L;
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		v.push_back(n);
	}

	solve();
}

N, M, L을 입력 받고 추가적인 입력(트럭의 무게)를 입력받아 벡터에 넣어줍니다.

 

while문 설명

 

int i = 0;
while(1){
if (i<N && cL + v[i] <= L)
{
		q.push(make_pair(W, v[i]));
		cL += v[i];
		i++;
}

i : 다리를 건너기 위해 기다리는 다음 트럭이 몇번째 트럭인가

 

if문의 조건은 아직 트럭이 다 다리위를 올라가지 않았고 i번째 트럭이 다리 위에 올라갈 수 있는가입니다.

cL(현재 다리 위에 올라가 있는 트럭들의 총 무게) + v[i] (i번째 트럭의 무게) 가 L(다리가 버틸수 있는 최대하중 이하여야 i번째 트럭을 올릴수 있습니다.

 

		int s = q.size();

		for (int j = 0; j < s ; j++)
		{
			if (!q.empty())
			{
				int ctime = q.front().first;
				int weight = q.front().second;
				q.pop();

				if (ctime - 1 != 0)
					q.push(make_pair(ctime - 1, weight));
				else
					cL -= weight;

			}
		}

s는 현재 다리위에 있는 트럭들을 한 번씩 이동시키기 위한 변수입니다.

4개의 트럭이 있다면 4번만 트럭들을 옮겨주죠

q가 비어있지 않다면 현재 트럭이 있는 겁니다.

그 트럭의 남은 다리길이(ctime)와 무기(weight)를 저장해 pop해줍니다.

만약 ctime에서 1을 빼도 0이 아니라면 아직 다리를 더 건너야 하는 거니깐 길이 1을 줄이고 큐에 다시 넣어줍니다

만약 0이라면 다리를 다 건넌 거니 그냥 cL에 해당 트럭만의 무게를 줄여주고 큐에 넣어주지 않습니다.

 

Time++;

if (i == N && q.empty())
	break;

모든 과정을 거친 후 Time을 1 추가해줍니다

만약 모든 트럭을 다 큐에 넣어준 상태고 q가 비어있다면 모든 트럭이 다리를 건넌 거니 break 해줍니다.