백준 13335. 트럭 (구현)

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

13335번: 트럭

구현 아이디어를 떠올리지 못해서 못풀었다. 풀이는 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/13335.cpp 을 참고했다. 

 

1. 특징

1) 구현

 

2. 구현 포인트

1) 다리의 칸별 무게를 배열로 저장함

2) 트럭의 이동을 진행할 때, 1번의 배열을 이용하여 한칸씩 무게를 앞으로 이동시킴.

3) 반복문을 다리에 기차가 없을 때 그만두게 함(트럭 queue이 empty이면으로 하면 x -> 마지막 트럭이 브릿지를 건너는 시간이 있기 때문에)

// 트럭의 이동을 진행하는 함수
void go(){
  for(int i = w-1; i > 0; --i)
    bridge[i] = bridge[i-1];
  bridge[0] = 0;
}

 

3. 코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int n, w, L;
int ans;
queue<int> truck; // 이동하는 트럭의 목록을 순차적으로 저장하는 변수
int bridge[101];
//다리가 비었는지 확인하는 함수
bool isEmpty()
{
    for(int i = 0; i < w; i++)
    {
        if(bridge[i] > 0)
            return false;
    }
    return true;
}
//트럭의 이동을 진행하는 함수
void go()
{
    for(int i = w-1; i > 0; i--)
    {
        bridge[i] = bridge[i-1];
    }
    bridge[0] = 0;
}
//다리 위 트럭의 무게를 계산하는 함수
int calculate()
{
    int sum = 0;
    for(int i = 0; i < w; i++)
    {
        sum += bridge[i];
    }
    return sum;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> w >> L;

    while(n--)
    {
        int i;
        cin >> i;
        truck.push(i);
    } 

    do
    {
        int tmp = calculate(); //현재 다리 위 트럭들의 무게
        tmp -= bridge[w-1]; // 나갈 트럭의 무게를 제외
        go();
        if(!truck.empty() && tmp + truck.front() <= L)
        {
            bridge[0] = truck.front(); truck.pop();
        }
        ans++;

    }while(!isEmpty());
    cout << ans;

}