Sandor의 개발 일지

Make real your dreams

1 분 소요

Question

Q Q2

Solution

  • 다리 위의 트럭을 queue에 담는다. q.empty()면 모든 트럭이 통과했다고 간주한다.
  • 다리 위의 트럭의 경과 시간을 관리할 runtime[10001]을 선언한다.
  • 경과 시간 answer에 따라 while을 돌리고 q에 있는 트럭들의 runtime을 증가시킨다.
    이 때 트럭의 runtime이 다리의 길이와 같아지면 트럭은 통과했다고 볼 수 있다.
  • (다리의 무게 - 다리 위의 트럭 무게의 합) > 0 이면,
    이 차보다 같거나 같은 트럭이 다음 대기 순번에 있다면 다리 위로 올린다.

Cord

#include <vector>
#include <queue>

using namespace std;

int runtime[10001];     // 다리위 트럭의 경과 시간

// 다리 위 트럭의 무게 합
int sumWeightOnBridge(queue<int> q, vector<int>& truck_weights)
{
    int sum = 0;
    while (!q.empty())
    {
        int idx = q.front();
        q.pop();
        sum += truck_weights[idx];
    }

    return sum;
}

// 다리 위 트럭의 경과 시간 증가
void runningTime(queue<int>& q, int bridge_length)
{
    queue<int> copyQ = q;

    // 트럭 각각의 경과 시간 증가
    while (!copyQ.empty())
    {
        int idx = copyQ.front();
        copyQ.pop();
        runtime[idx] += 1;
    }

    // 가장 먼저 출발한 트럭이 다리를 건넜는지 확인
    if (!q.empty() && runtime[q.front()] >= bridge_length) { q.pop(); }
}

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    int answer = 1;
    int nextIdx = 0;
    queue<int> q; // 출발한 다리위 트럭
    q.push(nextIdx);   // 가장 처음의 트럭 Idx
    nextIdx++;

    while (!q.empty())
    {
        answer++;   // 시간의 경과
        runningTime(q, bridge_length);  // 다리 위 트럭의 시간 경과
        int diff = weight - sumWeightOnBridge(q, truck_weights); // 다리 무게와 다리 위 트럭의 무게 합의 차
        
        // diff의 무게가 남고 다음 트럭이 이보다 작거나 같을때 추가 시키기
        if (nextIdx < truck_weights.size() && 0 < diff && truck_weights[nextIdx] <= diff)
        {
            q.push(nextIdx);
            nextIdx++;
        }
    }

    return answer;
}

Result

Result

참고