[프로그래머스] [C++] 다리를 지나는 트럭

문제 풀이

 

#include <string>
#include <queue>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    // 다리를 지나고 있는 트럭의 배열
    queue<int> across_truck;
    // 다리 위에 있는 트럭의 무게
    int max_size = 0;
    // 트럭의 무게
    int size = 0;
    
    // 각 트럭을 반복문으로 돌면서
    for(int i = 0; i < truck_weights.size(); i++){
        size = truck_weights[i];
        
        while(1){
        	// 다리에 트럭이 한 대도 없으면
            if(across_truck.empty()){
            // 트럭이 다리 위에 올라가고 해당 트럭의 무게를 추가. 시간 증가
                across_truck.push(size);
                max_size += size;
                answer++;
                break;
            }
            
            // 다리 길이만큼 트럭이 꽉 차있으면
            else if(across_truck.size() == bridge_length){
            	// 트럭이 나가고 그 무게도 뺀다
                max_size -= across_truck.front();
                across_truck.pop();
            }
            
            // 다리에 트럭이 있는데
            else{
                // 트럭이 한 대 더 들어가면 무게가 넘어갈 경우
                if(size + max_size > weight){
                	// 0을 추가함으로써 트럭이 한 칸 앞으로 움직였다는 것(시간의 증가)를 표현.
                    // 무게는 증가하지 않는다.
                    across_truck.push(0);
                    answer++;
                }
                
                // 한 대 더 들어가도 무게가 넘지 않는다면
                else{
                	// 트럭이 한 대 더 진입한다. 무게와 시간 또한 증가.
                    across_truck.push(size);
                    max_size += size;
                    answer++;
                    break;
                }
            }
        }       
    }
    
    return answer + bridge_length;
}

 

 자칫 헷갈리거나 어려워보일 수 있는 문제였으나 문제를 잘게 나누어 한 부분씩 처리하면 생각보다 해결의 실마리가 눈에 빨리 띌 수 있다는 것을 알려준 문제였습니다. 

 

 

 

문제 링크

 

 

programmers.co.kr/learn/courses/30/lessons/42583?language=cpp

코딩테스트 연습 - 다리를 지나는 트럭