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

📢 문제

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

📢 알고리즘

구현, 큐

📢 풀이

#include <iostream>
#include <queue>

using namespace std;

pair<int, int> car[1000];
int n, w, L;

int main()
{
  queue<pair<int, int>> q; //다리 위에 있는 트럭

  cin >> n >> w >> L;

  for (int i = 0; i < n; i++)
  {
    cin >> car[i].first;
  }

  int idx = 0;
  int time = 1; //현재시각
  int sum = 0;  //다리 위 무게합

  while (idx < n)
  {
    //뺄것 있으면 out
    //ex. 들어갈때 time=1, time=3이 되면 나감 -> time끼리의 차가 w이면
    if (!q.empty() && time - q.front().second == w)
    {
      sum -= q.front().first;
      q.pop();
    }

    //무게합 검증 통과하면
    if (sum + car[idx].first <= L)
    {
      //다리에 올림
      if (q.size() < w)
      {
        car[idx].second = time; //다리 위에 올린 시간 기록
        sum += car[idx].first;
        q.push(car[idx]);
        idx++;
      }
    }
    time++;
  }
  cout << time + w - 1;
}

• pair<int, int> car[1000]; : (무게, 큐에 들어간 시각(다리에 올라간 시각))

• 큐 : 다리 위에 있는 트럭

• 처음에 큐를 생각했다가 각 트럭이 다리 위에 머무는 시간을 각각 관리해줘야 해서, 내용물을 일일이 탐색하기 힘든 큐는 적합하지 않다고 생각했다. 그래서 시작 인덱스, 끝 인덱스를 둬서 다리 위에 있는 트럭들을 관리했다. 하지만 인덱스 관리가 너무 복잡!

  • 코드 짜기가 너무 복잡하면.. 애초에 설계부터 잘못됐을 가능성이 많다. 문제는 생각보다 어렵지 않다. 코드로 옮기기 전에 좀더 쉽게 풀 수 있는 방법이 없는지 다시 생각해보자.

• 큐를 사용하려면 현재 시각 - 각 트럭이 다리 위에 올라간 시각으로 각 트럭이 다리 위에 머무는 시간을 그때그때 계산해주면 된다!

  • 💡 이렇게 현재 시각 - 큐에 들어간 시각을 이용해서 큐에 머무는 시간을 따로 저장해두지 않고도 활용하는 문제가 몇 번 있던 것 같다!!

• q.pop(); q.front();운 반드시 if(!q.empty())라는 조건 안에서 사용하자!