[백준] 13335 - 트럭 (C++)

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

강을 가로지르는 하나의 차선으로 된 다리가 있다. 이 다리를 n개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리의 길이는 w 단위길이이며, 각 트럭들은 하나의 단위시간에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 즉, 다리 위에는 w대의 트럭만 동시에 올라갈 수 있다. 다리 위에 올라가 있는 모든 트럭들의 무게의 합은 다리의 최대하중인 L을 넘을 수 없다.

예시

다리의 길이 w와 다리의 최대하중 L, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어질 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ n ≤ 1,000
• 1 ≤ w ≤ 100
• 10 ≤ L ≤ 1,000
• 1 ≤ 트럭의 무게 ≤ 10

 

queue<pair<int,int>>를 선언해 다리에 올라가 있는 트럭의 인덱스와 해당 트럭이 다리에서 내려오는 시간을 저장한다. 트럭의 순서를 바꿀 순 없기 때문에 만약 다리에 올라가 있는 트럭들의 무게가 최대하중을 넘기게 되면 queue를 비워가면서 다른 트럭이 올라갈 수 있을 때까지 반복하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. n, w, L, 트럭 무게 정보 입력받기
2. 시간을 기준으로 for문 진행
   1. w_sum: 현재 다리 위에 있는 모든 트럭의 무게를 저장 / left: 다리 위에 아직 안 올라온 맨 앞 트럭의 인덱스
   2. queue가 비어있지 않고, 지금 시간이 가장 앞에 있는 트럭이 다리를 벗어날 시간과 같다면 w_sum에서 맨 앞 트럭 무게를 빼고 queue에서 pop()하기
   3. 다음 트럭이 다리 위에 올라와도 최대하중을 넘지 않는다면,
      1. queue에 해당 트럭의 인덱스와 다리를 벗어나는 시간을 pair로 저장하고, w_sum에 트럭 무게를 더하고 left에 1 더하기
      2. left가 n 이상이라면 남은 트럭이 없으므로, queue에 마지막으로 추가한 트럭이 다리를 벗어나는 시간을 출력하고 프로그램 종료

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1회차

• 아직 다리를 건너지 않은 트럭을 다리 위에 올렸을 때
  • 최대하중을 넘기지 않는다면 트럭을 queue에 추가 / 넘긴다면 queue pop()하기
• tm 변수 값을 더하고 빼면서 정확하게 계산되지 않은 것 같음 

#include <iostream>
#include <queue>
#define pii pair<int,int>
using namespace std;

int n,w,l,tr[1001];
queue<pii> q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> w >> l;
    for (int i=0; i<n; i++) cin >> tr[i];

    int w_sum=0,in=0,left=0,tm=0;
    while (1) {
        if (w_sum+tr[left]<=l) {
            w_sum += tr[left];
            tm++;
            q.push({left,tm+w});
            left++;
            if (left>=n) {
                cout << q.back().second;
                return 0;
            }
        }
        else {
            in = q.front().first;
            tm = q.front().second-1;
            q.pop();
            w_sum -= tr[in];
        }
    }
}

 

---

정답 코드

#include <iostream>
#include <queue>
#define pii pair<int,int>
using namespace std;

int n,w,l,tr[1001];
queue<pii> q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> w >> l;
    for (int i=0; i<n; i++) cin >> tr[i];

    int w_sum=0,left=0;
    for (int i=1; ; i++) {
        if (!q.empty()) {
            auto [idx,tm] = q.front();
            if (tm==i) {
                w_sum -= tr[idx];
                q.pop();
            }
        }
        if (w_sum+tr[left]<=l) {
            q.push({left,i+w});
            w_sum += tr[left];
            left++;
            if (left>=n) {
                cout << i+w;
                return 0;
            }
        }
    }
}