[알고리즘] 프로그래머스 - 다리를 지나는 트럭 c++

문제 링크

다리를 지나는 트럭 : Level2

틀린이유

• 순서대로 들어온 순서대로 나가니까 큐로 구현해야겠다
• 다리 위에 있을 수 있는 트럭의 개수가 상이하다보니 이를 구현하는 게 포인트
• 한번에 건널 수 있을 때마다 나눠서 풀려고 함
• 그런데 여기서 완전 잘못 생각함! 😢
  • 최대 10kg 이고 트럭이 [5,5,4] 일 때
  • 나의 풀이로는 한 번에 2개까지만 갈 수 있지만,
  • 실제로는 5가 나가고 나면 4가 바로 위에 올라올 수 있기 때문에 단계별로 시간 계산하면 오류가 생김!!!

문제 분석

문제

• 트럭 여러 대가 일차선 다리를 순서대로 건너려고 한다
• 구) 모든 트럭이 다리를 건너는데 최소 몇 초가 걸릴까?
• 트럭은 1초에 1 다리 길이만큼 움직인다

입력

• 다리 길이 == 다리에 올라갈 수 있는 트럭 수 : 1≤ bridge_length ≤ 10^4
• 다리가 버틸 수 있는 무게 : 1 ≤ weight ≤ 10^4
• 트럭의 개수 : 1≤ truck_weight ≤ 10^4
• 트럭의 무게 : 1≤ truck_weight[i] ≤ weight

구현 방법

1. 순서대로 트럭이 들어가고 나가야하니까 queue
2. 트럭을 움직이는 것을 어떻게 표현할 수 있을까?
   • 큐에다가 가능하면 트럭 무게를 넣고, 가능하지 않으면 트럭 대신 0을 넣자! (트럭 무게 1이상이므로)
   • 큐가 다리 끝에 도달하면 뒤에 트럭의 개수가 몇 개인지와 상관없이 Q.size()는 bridge_length와 일치하게 됨!
   • 다리 끝에 도달하면 큐에서 제거해줌
3. 마지막 트럭은 무조건 bridge_length만큼 건너간다

전체 코드

#include <bits/stdc++.h>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    queue<int> Q;
    int i=0;
    int w = 0;
    while (true){
        if (i == truck_weights.size()){
            answer += bridge_length;
            break;
        }
        
        answer++;
        
        if (Q.size() == bridge_length){
            w -= Q.front();
            Q.pop();
        }
        
        if (w+truck_weights[i] <= weight){
            Q.push(truck_weights[i]);
            w += truck_weights[i];
            i++;
        }
        else Q.push(0);
        
    }
    
    return answer;
}