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

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

13335번: 트럭

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[10001];

int main()
{
   int N, W, L;
   cin >> N >> W >> L;

   queue<int>q;

   for (int i = 0; i < N; i++)
   {
		cin >> arr[i];
	}
   
   int total = 0, cnt = 0;
   for(int i=0; i<N; i++)
   {
      while(1)
      {
         if(q.size() == W) //다리가 꽉차면
         {
            total -= q.front(); //맨 앞에 제거
            q.pop();
         }

         if(total + arr[i] <= L) //종료조건
         {
            if(i == (N-1)) cnt+=W; //마지막 계산 후 다리 위에 남은 값 처리
            break;
         } 
         else
         {
            q.push(0); //사이즈 유지위해 빈값넣기
            cnt++; //값이 들어가서 이동했으므로 + 1
         } 
        
      }
      q.push(arr[i]);
      total += arr[i]; //값 저장
      cnt++; //다리로 이동했으므로 + 1
   }

   cout << cnt;
   return 0;
}

큐를 활용한 문제이다.

 

큐에 값을 하나씩 넣어주다가 큐의 사이즈가 다리 길이와 같아지면 맨 앞의 값을 제거한다. (다리 밖으로 이동)

만약 현재값과 다음들어올 값의 합이 최대하중을 초과한다면, 큐에 0을 넣어서 앞에 값이 혼자 이동하는걸 표현한다.

이렇게 되면 큐의 사이즈를 자연스럽게 맞춰줄수 있다.

이때도 마찬가지로 값이 들어가서 앞의 값이 이동하게 되는 것이므로 + 1을 해준다.

 

그리고 계산의 마지막에 다리 길이만큼 더해줘야 한다.

이는 위 코드대로 하면 마지막에 다리에 남은 값들은 처리를 안해주기 때문이다.

마지막으로 남아있던 값이 다리에 들어오고 끝나는데, 이 상태에서 다리에 값이 남아있기 때문에 이를 처리해줘야 한다.

다리 길이만큼 더해주는 이유는 마지막으로 들어온 값이 무사히 나가기 위해선 다리 길이만큼 이동해야 하기 때문이다.