[2025.03.13] 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

 

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7, 4, 5, 6]
1~2	[]	[7]	[4, 5, 6]
3	[7]	[4]	[5, 6]
4	[7]	[4, 5]	[6]
5	[7, 4]	[5]	[6]
6~7	[7, 4, 5]	[6]	[]
8	[7, 4, 5, 6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

 

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

 

제한사항

• bridge_length는 1이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

 

입출력 예

bridge_length			weight	truck_weights	result
2			10	[7, 4, 5, 6]	8
100			100	[10]	101
100			100	[10, 10, 10, 10, 10, 10, 10, 10, 10, 10]	110

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <deque>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    deque<pair<int, int>> bridge;
    int truck_index=0;
    int time;
    
    // 첫 번째 트럭 다리 위로 올리기
    bridge.push_back({truck_weights[0], 1});
    truck_index++;
    time=1;
    
    while(!bridge.empty())
    {
        // 다리 위 트럭 유지할지 지나갈지 체크
        if(bridge.front().second>bridge_length)
        {
            bridge.pop_front();
        }
        
        // 현재 다리 위의 트럭들의 전체 무게
        int sum=0;
        for(int i=0; i<bridge.size(); i++)
        {
            sum+=bridge[i].first;
        }
        
        // 다리 위로 더 들어올 수 있는지 체크
        if(truck_index<truck_weights.size()&&weight-sum>=truck_weights[truck_index])
        {
            bridge.push_back({truck_weights[truck_index], 1});
            truck_index++;
        }
        
        // 다리 위에 있던 시간 업데이트
        for(int i=0; i<bridge.size(); i++)
        {
            bridge[i].second++;
        }
        
        // 시간 업데이트
        time++;
    }
    
    answer=time-1;
    return answer;
}

 

 

먼저 현재 다리 상황을 알 수 있는 변수를 하나 만들어 주어야 할 것이라고 생각했다. 다리 위로 올라간 트럭이 먼저 나온다고 생각하여 일단 bridge라는 이름의 deque를 만들어주었다. 그리고 요소로는 pair를 이용하여 int형 데이터 두개를 넣도록 해주었는데 하나는 트럭의 무게를 저장하고 하나는 해당 트럭이 도로에서 얼마나 갔는지를 나타낼 것이다. 그리고 다음으로 다리에 올라갈 트럭을 가리키는 index인 truck_index를 선언하고 경과 시간을 표시할 time이라는 변수를 선언한다.

 

일단 첫 번째 트럭부터 올리고 본다. bridge에 truck_weights의 0번째 트럭을 push_back하여 올려주었다. 그리고 올라간 순간 트럭의 길이 중 1을 움직인 것이니 움직인 거리는 1을 해주었다. 첫 번째 트럭이 올라갔으므로 truck_index는 1 증가하여 업데이트해주고 time은 1 늘어난 것으로 한다.

 

이제 반복문에서 트럭을 다리에 올리고 움직이고 내리고를 구현해줄 것이다. 반복문 안에서는 5가지 일을 한다.

1. 가장 앞에 있는 트럭이 다리 끝까지 갔는지 확인하기
2. 현재 다리 위의 트럭들의 전체 무게 계산
3. 현재 상태에서 다리 위에 트럭이 더 들어와도 되는지 확인하기
4. 다리 위에 있던 트럭들
5. 경과 시간 업데이트

반복문을 시작하면 가장 앞에 있는 트럭이 다리 끝가지 가서 다리에서 내려왔는지를 확인한다. bridge에서 가장 앞에 있는 요소를 가져와서 트럭이 움직인 거리를 체크한다. 다리의 길이보다 길게 나왔다면 다리에서 벗어난 것이므로 bridge에서 pop_front 해준다.

다음으로 현재 다리 위의 트럭들의 전체 무게를 구한다. 이는 아래 다리 위로 트럭이 더 올라올 수 있는지 체크할 때 사용한다. 반복문을 이용해 간단하게 bridge 위에 있는 트럭들의 무게를 모두 더해서 sum에 저장한다.

이제 현재 다리 위에 있는 트럭의 전체 무게를 알고 있으니 다리위에 다른 트럭이 더 올라와도 되는지 확인한다. 일단 들어올 트럭의 인덱스가 유효한지 확인하고 그 다음 전체 트럭의 무게에 다음 트럭의 무게를 더해도 기준 무게를 넘어가지 않는지 확인한다. 만약 새로 트럭이 들어와도 되는 상황이라면 bridge 맨 뒤에 새로운 트럭을 push_back 한다. 이때 올라오는 순간 1 거리만큼 이동한 것으로 하여 초기화한다. 그리고 다음 트럭의 인덱스를 업데이트한다.

이제 다리 위에 남은 트럭들을 전부 1씩 앞으로 이동하게 한다. 즉 bridge[i].second를 하나씩 늘리는 것이다.

마지막으로 경과 시간을 업데이트 하면 된다.

 

반복문이 끝나는 것은 bridge에 하나의 차도 남아있지 않을 때이다. 단 반복문이 끝날 때 다리에 차가 없어도 경과시간을 1 업데이트 하고 끝나기 때문에 정답은 time-1이다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스