[BOJ 13335] 트럭

문제 분석

• 시간제한 1초 ⇒ big-O계산으로 약 1억
• 처리해야하는 트럭의 갯수 최대 1000개, 다리에 올라갈 수 있는 트럭의 갯수 최대 100개 1억 > 1000*1000 (이중 반복문 가능)
• <queue> 를 이용해 다리를 건너기전 대기중인 트럭들을 관리한다.
• <vector> 를 이용해 다리위에 있는 트럭들을 관리한다.
• 아래 행위를 1 단위시간마다 대기하는 트럭의 queue가 비어질 때 까지 반복한다.
  • 최대 w개의 트럭이 무게 합이 l이 안되게 다리위로 올린다.
  • 현재 다리위에 올려져 있는 무게 와 새로 들어올 트럭의 무게의 합이 l을 넘지 않으면 트럭을 다리로 올린다.
  • 다리위에 올려져 있는 트럭마다 이동 거리 변수를 만들어 다리에서 빠져나올때까지 이동거리를 증가시킨다.
  • 다리위에 맨앞에 있는 트럭의 이동거리가 l이 되면 그 트럭을 다리에서 뺀다.
• queue가 비면 vector가 빌때까지(트럭들이 모두 다리를 벗어날 때 까지) 반복한다.
  • 다리위에 올려져 있는 트럭마다 이동 거리 변수를 증가시킨다.
  • 다리위에 맨앞에 있는 트럭의 이동거리가 l이 되면 그 트럭을 다리에서 뺀다.

queue<int> trucks;
vector<pair<int, int>> bridge;
int n, l, w, x, cnt, sum;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> w >> l;
    while (n--) {
        cin >> x;
        trucks.push(x);
    }
    while (!trucks.empty()) {
    	//트럭의 이동거리가 다리의 길이와 같아지면
        if (!bridge.empty() && bridge.front().second == w) {
            sum -= bridge.front().first;
            //트럭의 무게를 다리위에 올려져 있는 무게에서 빼고
            bridge.erase(bridge.begin());
            //트럭을 다리에서 지운다.
        }
        //대기중인 트럭이 다리위에 올라갈 수 있으면
        if (l >= sum + trucks.front()) {
            sum += trucks.front();//트럭의 무게를 다리위에 올려 있는 무게에 더해주고
            bridge.emplace_back(trucks.front(), 0);//트럭을 다리위에 올리고
            trucks.pop();//대기열에서 뺀다.
        }
        for (int i = 0; i < bridge.size(); i++) {//다리위 트럭들
            bridge[i].second++;//이동거리를 1씩 증가시킨다
        }
        cnt++;//단위시간 1증가
    }
    while (!bridge.empty()) {//다리가 빌때까지
    	//다리위에 있는 트럭에 대한 코드 (위와 동일)
        if (bridge.front().second == w) {
            sum -= bridge.front().first;
            bridge.erase(bridge.begin());
        }
        for (int i = 0; i < bridge.size(); i++) {
            bridge[i].second++;
        }
        cnt++;//단위시간 1증가
    }
    cout << cnt << "\n";
    return 0;
}

처음에 트럭이 다리를 건넜을 때 처리해주는 코드를 (줄 15-20) while문 마지막에 작성했다.
이렇게 되면 트럭을 다리에서 빼는 작업을 비효율적으로 처리하므로 cnt(단위시간)값이 더 크게 나온다.

느낀 점

• 문제를 보고 대기줄에 관한 queue, 다리에 관한 queue를 만들어 문제를 풀려했다.
  그러다 트럭마다 이동거리에 대한 변수를 만들고 싶어 다리에 있는 트럭을 처리하는 stl은 <vector>를 이용해야 겠다는 생각을 했다.
  그랬더니 문제가 어렵지 않게 풀렸다.
• 단위시간 마다 어떤 사건이 일어나야 하는지 적어가며 그 사건이 일어나도록 코드를 작성했다.
• 트럭마다 이동거리에 관한 변수를 만든건 꽤 좋은 생각이었다는 뿌듯한 생각이 든다.

시간 복잡도

• 트럭 대기줄 빌때 까지 반복 -> O(n) (n≤1000)
• 다리위 트럭들 이동 거리 증가 -> O(n) (n≤100)
  ⇒ O(n^2) (약 O(100,000))
• 다리 빌때 까지 반복 -> O(n) (n≤100)
• 다리위 트럭들 이동 거리 증가 -> O(n) (n≤100)
  ⇒ O(n^2) (약 O(10,000))
  
  ➣ O(n^2) (약 O(100,000))