백준 13335번 [트럭](C++) -yes6686- 티스토리

백준 문제 풀이: 13335 [트럭]

---

문제 링크: https://www.acmicpc.net/problem/13335

문제 설명:

트럭이 하나씩 다리를 건널 수 있으며, 다리는 한 번에 w대의 트럭과 최대 하중 l을 버틸 수 있습니다. 모든 트럭이 다리를 건너는 최소 시간을 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1001]; // 트럭의 무게를 저장하는 배열
int larr[1001]; // 다리 위에 있는 트럭들의 위치를 관리하는 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, w, l;
    cin >> n >> w >> l; // 트럭 개수, 다리 길이, 최대 하중 입력

    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 각 트럭의 무게 입력
    }

    int t = 0; // 경과 시간
    int s = 0; // 현재 다리를 건너고 있는 트럭의 시작 위치

    while (true) {
        int sum = 0;
        int currLengthW = 0; // 현재 다리 위에 있는 트럭 무게의 합
        
        // 현재 다리에 트럭을 올릴 수 있는지 확인
        for (int i = s; i < n; i++) {
            if (currLengthW + arr[i] > l) { // 최대 하중을 초과하면 종료
                break;
            }
            currLengthW += arr[i]; // 현재 다리 위에 있는 트럭 무게 갱신

            if (i == s) {
                larr[i]++; // 맨 처음 트럭의 다리 위치 증가
            } else {
                if (larr[i - 1] - larr[i] >= 2) {
                    larr[i]++; // 앞 트럭과의 거리 유지하며 위치 증가
                } else {
                    break;
                }
            }

            if (larr[i] > w) { // 다리 길이를 초과하면 다음 트럭으로 이동
                s++;
                currLengthW -= arr[i];
            }
        }

        t++; // 시간 증가
        if (s == n) break; // 모든 트럭이 다리를 건너면 종료
    }

    cout << t << '\n'; // 총 소요 시간 출력
}

예제 입력:

4 2 10
7 4 5 6

예제 출력:

8

---

코드 설명

• 핵심 알고리즘: 시뮬레이션을 이용하여 다리를 건너는 트럭의 상태를 추적합니다.
• 구현 세부사항:
  • 다리에 트럭을 올릴 수 있는지 확인하면서 무게를 누적합니다.
  • 다리 위의 트럭 위치를 관리하며, 최대 하중 및 다리 길이를 초과하는지 체크합니다.
  • 경과 시간을 증가시키며, 모든 트럭이 다리를 건널 때까지 반복합니다.
• 시간 복잡도: O(N²), 모든 트럭을 한 번씩 검사하며 최대 N번 반복

---

결과

트럭이 주어진 제한을 지키면서 다리를 건널 수 있도록 정확히 시뮬레이션합니다. 큐(Queue)를 활용한 시뮬레이션 문제를 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!