다리를 지나는 트럭

문제

가장 먼저 이 문제를 풀기 위해 설계를 시작하면서, 어떤 변수들이 필요할지부터 생각했다.

필요한 변수

int answer = 0;                      //답 
int time = 0;                        //시간계산
stack<int> remain;                   //남아있는 버스변수
int sum=0;                           //다리위에 올라가있는 버스무게 변수
int *bridge =new int[bridge_length]; //다리 정의
int check =truck_weights.size();     //전체 트럭의 수 변수
int finish = 0;                      //목적지에 도착한 트럭 수

이정도 변수가 필요하다고 생각했고 코드를 작성하기 시작했다.

일단 총 트럭을 Stack에 넣는 것부터 시작했다. 하지만 그냥 넣으면 뒤집어서 들어가지 reverse를 이용해 vector를 뒤집고 그 뒤에 Stack에 넣어주었다.

그리고 while문을 설계해주었는데,
while문의 조건을 finish변수와 check 변수가 일치하지 않을경우
-> 모든 트럭이 도착하지 못했을 경우로 설계해주었다.

또한 bridge라는 변수를 다리라고 이미지를 그리고 한칸씩 당기면서 계산해주었고, 이를 토대로 코드를 작성했다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
#include <array>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0; //답 
    int time = 0;   //시간계산
    stack<int> remain;  //남아있는 버스변수
    int sum=0;      //다리위에 올라가있는 버스무게 변수
    int *bridge =new int[bridge_length]; //다리 정의
    int check =truck_weights.size();     //전체 트럭의 수 변수
    int finish = 0;                      //목적지에 도착한 트럭 수
    for (int i = 0;i < bridge_length;i++) {
        bridge[i] = 0;
    }
    reverse(truck_weights.begin(), truck_weights.end());
    for (int i = 0;i < truck_weights.size();i++) {
        remain.push(truck_weights[i]);
    }
    while (check!= finish) { //모든 트럭이 도착지에 도달할때까지 while문
        for (int i = bridge_length-1;i-1 >=0;i--) {   //다리를 한칸씩 당김
            if (i == bridge_length - 1) {             //for문의 첫번째 경우에서
                if (bridge[i] != 0) {                 //다리의 마지막에 트럭이 있을 경우
                    sum -= bridge[i];                 //sum에서 마지막에 있는 트럭을 빼줌
                    finish++;                         //도착한 트럭의 수를 하나 늘림
                }
            }
            bridge[i] = bridge[i - 1];                //다리 위에 있는 트럭을 한칸 씩 당김
        }
        if (remain.empty()||sum + remain.top() > weight) {  //stack이 비어있지 않고 허용 무게보다 무거울 경우
            time++;                                         //시간추가해줌
            bridge[0] = 0;                                  //처음에 0을 삽입
            continue;
        }
        bridge[0] = remain.top();                           //그게아닐경우 0에 위치에 다음 차량을 넣음
        sum += bridge[0];                                   //총 무게를 더함
        remain.pop();                                       //stack에서 pop을 해줌
        time++;                                             //시간을 더해줌
    }
    answer = time;    //그렇게 해서 while문을 빠져나왔을 경우 time이 답임
    return answer;
}

후기

처음에 다리의 이미지를 생각해내는게 어려웠지만 다리의 이미지만 그리고 그것을 변수로 구현할 수 있다면 그 뒤는 금방 풀렸던 것 같다.