13335번 트럭

https://www.acmicpc.net/problem/13335

 

처음에는 Greedy 문제인줄 알았다.

 

로직 순서 호출만 조심하면 되고, 나머지는 구현이다.

 

1. 한 칸 씩 이동 → 트럭 제거 → 새로운 트럭 추가 순서로 호출

2. 무게 총 합에서 제거한 트럭의 무게를 뺄 때, v.erase(itr)를 나중에 해준다. 먼저하면, itr이 자동 증가하기 때문에 그 다음 원소(트럭)의 무게가 빼진다.

3. 새로운 트럭을 추가할 때, index와 현재 다리에 올라가 있는 트럭들의 무게 총합(total_weight)를 올라갈 트럭의 무게까지 고려하여 if 조건문을 잘 따진다.

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 1010
// https://www.acmicpc.net/problem/13335
int a[MAX];
int n, w, L;

/*
* w : 다리 길이
* L : 다리의 최대 하중
*/
int simulation() {
    int t = 0;
    
    vector<pair<int, int> > bridge; // 다리
    int total_weight = 0; // 다리에 올라가있는 트럭들의 무게 총 합
    int index = 0; // 현재 트럭의 순서(인덱스)

    while (true)
    {
        // 한 칸 이동
        if (!bridge.empty()) {
            for (auto& i : bridge) {
                i.second += 1;
            }
        }

        // 다리 지나간 트럭 제거(새로운 트럭을 추가하는 로직보다 먼저 와야한다.)
        // 그래야, bridge.empty()라면, break 할 수 있다.
        while (!bridge.empty())
        {
            auto itr = bridge.begin();
            if (itr->second == w) {
                total_weight -= itr->first; // 무게 총합에서 뺀다. ★순서주의 : 계산부터 먼저 한 후, erase 해야함.
                bridge.erase(itr); // 다리에 올라가 있는 맨 앞 트럭 제거
            }
            else {
                break;
            }
        }

        // 새로운 트럭 추가
        if (index < n && bridge.size() + 1 <= w && total_weight + a[index] <= L) {
            bridge.push_back({ a[index], 0 });
            total_weight += a[index++];
        }

        // 시간 경과
        ++t;

        // 탈출
        if (bridge.empty()) {
            break;
        }
    }

    return t;
}

int main()
{
    cin.tie(0);

    scanf("%d %d %d", &n, &w, &L);
   
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    printf("%d\n", simulation());

    return 0;
}