[백준/C++] 알고리즘 13335번 - 트럭

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 13335번 - 트럭을 풀어보도록 하겠습니다.

 

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

13335번: 트럭

[문제 접근]

가장 오래걸리는 시간을 확인해보았을 때 n * w+로 100,001라는 것을 확인할 수 있습니다.

제한시간은 1초로 넉넉해서 완전탐색으로 접근했습니다. 그리고 가장 먼저 다리에 통과한 트럭이, 가장 먼저 빠져나오기 때문에 큐를 이용하였습니다.

 

[풀이 전략]

1. for문 w*n+1만큼 돈다.

2. 현재 입구에 ㅣ대기중인 트럭을 가리키는 pt 변수, 다리 위에 올라와 있는 트럭을 저장할 q, 다리위의 총 무게 currL을 생성합니다.

3-1) pt가 n이 아닌 경우

- 만약 currL과 arr[pt]의 합이 L이하라면 -> q에 arr[pt]를 대입하고, currL에 arr[pt]를 더하고 pt 증가시킵니다.

- 만약 currL과 arr[pt]의 합이 L을 초과하면 -> 0을 q에 삽입합니다.(여기서 0은 정지역할)

3-2) pt가 n인 경우

- -1을 삽입합니다. (여기서 -1은 종료역할)

4. q의 크기가 w와 같으면 q를 하나 꺼내는데 -1이면 tot = i로 초기화하고 break를 합니다. 만약 꺼낸 것이 0이 아니라면 currL에 그것을 빼줍니다. 

5. tot이 값이 0이라면 최악의 상황임을 의미하므로 w*n+1을 대입합니다.

6. tot을 출력합니다.

 

[코드]

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

// 트럭

int n, w, l ;

int arr[1'001];
int tot ; 
int pt ;
int currL; 

queue<int> q  ; 

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n >> w >> l ;

    for(int i = 0 ; i < n ; i++) cin >> arr[i];

    for(int i= 0 ; i < w*n+1 ; i++){
        if(q.size() == w) {
            int cur = q.front(); q.pop();  
            if(cur == -1){tot = i ;break ;} 
            if(cur != 0 ) currL -= cur;  
        }
        if(pt != n){
            int nxt = arr[pt];
            if((currL + nxt) <= l){ q.push(nxt); currL += nxt; pt++; }
            else {q.push(0);}
        }
        else{
            q.push(-1);
        }

    }
    if(tot == 0) tot = w*n+1 ;    

    cout << tot; 
}

 

[배울 점]

- 경계지점을 명확히 하고 문제풀이에 들어가기