13335번: 트럭

Memo

• 오른쪽에서 대기 중인 트럭이 순서가 바뀌지 않고 들어온 순서대로 나간다는 부분에서 queue를 떠올릴 수 있었습니다.
• 다리에 있는 트럭을 먼저 움직이고 나서 오른쪽에서 대기하고 있는 트럭이 들어올 수 있는지를 확인 하는 방법을 떠올렸습니다.
• 다리의 최대 길이는 정해져 있고, 다리의 첫 번째 인덱스와 마지막 인덱스를 정해 주면 한 칸씩 미는 것은 문제가 없다 생각했습니다.
• 문제에서 요구하는 것이 다리를 건넌 트럭이 아니므로 오른쪽에 대기중인 트럭과 다리 위의 트럭 외에는 신경쓰지 않습니다.

Code

제출 날짜

2021/03/28

메모리

2016 KB

시간

0 ms

#include <iostream>
#include <queue>

int n, w, L;
std::queue<int> q;
int bridge[102];
int bridge_begin, bridge_end;
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int tmp;

	input_faster();
	std::cin >> n >> w >> L;
	bridge_begin = 1;
	bridge_end = w;
	for (int i = 0 ; i < n ; i++)
	{
		std::cin >> tmp;
		q.push(tmp);
	}
	ans = 0;
}

int bridge_state()
{
	int cnt = 0;

	for (int i = bridge_begin ; i <= bridge_end ; i++)
		if (bridge[i])
			cnt++;
	return (cnt);
}

void bridge_move()
{
	for (int i = bridge_begin ; i <= bridge_end + 1 ; i++)//bridge_end + 1 is for begin_end to 0
		bridge[i - 1] = bridge[i];
}

int bridge_weight()
{
	int weight = 0;

	for (int i = bridge_begin ; i <= bridge_end ; i++)
		weight += bridge[i];
	return (weight);
}

void move_action()
{
	int top, weight;

	bridge_move();
	top = q.front();
	weight = bridge_weight();
	if (!q.empty() && weight + top <= L && !bridge[bridge_end]) // when truck can move in right side, and birdge of end side is clear
	{
		q.pop();
		bridge[bridge_end] = top;
	}
}

void solve()
{
	while (!q.empty() || bridge_state()) //when q is not empty, or bridge is not clear
	{
		move_action();
		ans++;
	}
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}