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

프로그래머스의 다리를 지나는 트럭(Lv2) 문제이다.

[ 문제풀이 ]

1) 본인은 트럭이 다리에 올라감과 동시에 다리에서 내려가는 시간을 저장해 주었다.

   예를 들어서 1번 트럭이 1초에 다리에 올라가고, 다리의 길이가 5라면, 이 트럭은 6초에 다리에서 내려갈 것이다.

   이렇게 트럭이 다리에 올라가는 순간, 다리에서 내려오는 시간을 알 수 있기 때문에 이 시간을 저장해 주었다.

   그래서 만약, 현재 트럭이 다리의 무게를 초과해서 올라갈 수 없는 상황이라면, 현재의 시간을 "현재 다리에서 가장 앞에

   있는 트럭이 내려가는 시간" 으로 바로 건너뛰어 주었다.

   예를 들어서

   다리의 길이 = 5 / 다리가 버틸 수 있는 무게 = 10kg / 1초에 10kg인 1번 트럭이 올라가 있는 상태 /

   현재 시간은 2초 / 10kg인 2번 트럭이 올라가려는 상황

   이라고 가정을 해보면, 여기서 2, 3, 4, 5초를 시간만 ++ 해줘도 되지만, 그럴 필요 없이, 2초라는 시간을 바로 6초로

   바꿔주고 트럭을 바로 올려주었다. 이런식으로 구현을 하였다.

   즉, 본인이 구현한 내용을 정리해보면 다음과 같다.

   1. 현재 트럭이 다리에 올라갈 수 있다면 ? = 그대로 올려준다.

   2. 올라갈 수 없다면 ? = 현재 다리위에 있는 트럭들 중, 가장 앞에 있는 트럭들 부터 순차적으로 다리에서 내려가는

     시간으로 시간을 건너뛰어 주면서 현재 트럭이 올라갈 수 있는 시간이 될 때 까지 시간을 넘겨준다.

   이렇게 구현을 해 주었는데, 예제 입력까지는 모두 맞았지만, 틀리는 경우가 발생하였다.

   바로 이런 경우였다.

   다리의 길이 = 1 / 다리가 버틸 수 있는 무게 = 10 kg /

   트럭의 무게를 순서대로 나타내면 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } 이런 경우였다.

   이 경우 시간별로 설명을 해보자면, 1초에 1번트럭이 올라가고 2초에 1번트럭이 내려오면서 2번트럭이 올라가고,

   3초에 2번 트럭이 내려오면서 3번트럭이 올라가고..... 이런식으로 진행된다.

   하지만 ! 본인이 위에서 말한대로만 구현을 하다보니, 5초에 5번 트럭이 올라가지 못하는 상황이 생겼다.

   애초에, 5초에 5번 트럭이 올라갈 수 있는 상황임에도, 올라갈 수 없는 조건문에 걸려버리면서 계산이 꼬여버리는

   경우가 발생해서, 위의 과정에서 한 단계를 더 추가해주었다.

   1. 현재 시간에 다리에서 내려갈 트럭이 있으면, 트럭을 내려준다.

   2. 현재 트럭이 다리에 올라갈 수 있으면 올려준다.

   3. 그게 아니라면, 위에서 말한듯이 시간을 건너뛰는 과정을 진행해준다.

   이렇게 총 3단계로 구현을 했더니 pass를 받을 수 있었다.

[ 소스코드 ]

#include <string>
#include <vector>
using namespace std;
int EndTime[10010];
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    int Total = 0;
    int Time = 1;
    int Front = 0;
    int Idx = 0;
    for (int i = 0; i < truck_weights.size(); )
    {
        int CS = truck_weights[i];
        /* 1. 현재 시간에 다리에서 내려갈 트럭이 있으면, 트럭을 내려준다. */
        for (int j = Front; j < i; j++)
        {
            if (EndTime[j] == Time)
            {
                Total = Total - truck_weights[j];
                Front++;
            }
        }
 
        /* 2. 트럭이 올라갈 수 있는 경우 */
        if (Total + CS <= weight)
        {
            Total = Total + CS;
            EndTime[i++] = Time + bridge_length;
            Time++;
        }
        /* 3. 트럭이 올라갈 수 없는 경우 = 시간을 건너뛴다. */
        else
        {
            while (1)
            {
                if (Total + CS <= weight) break;
                Total = Total - truck_weights[Front];
                Time = EndTime[Front++];
            }
            Total = Total + CS;
            EndTime[i++] = Time + bridge_length;
            Time++;
        }
    }
    Time = EndTime[truck_weights.size() - 1];
    return Time;
}