[BOJ] 트럭 13335번 C++

2025. 4. 24. 13:35· Algorithm

 

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

Figure 1. 본문의 예에 대해 트럭들이 다리를 건너는 과정.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

 

접근 방식

 

다리를 큐로 시뮬레이션하고, 매 초마다 트럭을 한 칸씩 이동시키는 식으로 구현하면 된다

 

먼저, 다리의 길이인 w만큼 0으로 초기화된 큐를 만들고 매 초마다 이 큐를 pop하면서 트럭이 이동한 것으로 간주시킨다

이때, 시간 단위를 1씩 증가시키면서 트럭을 넣을 수 있다면 큐에 push하고 무게가 초과한다면 0을 push해서 빈 공간을 유지시킨다

따라서, 현재 큐 즉 다리에 있는 트럭 무게의 총합을 계속 계산하면서 다음 트럭을 올릴 수 있는지 체크하면 된다!

 

주의할 점은 마지막 트럭이 다리에서 빠져나갈때까지 초를 계산해야 하기 때문에 이전까지는 0을 push하고 마지막 트럭이 다리안에 들어갔다면 0을 push하지 않게 해야한다는 것!!

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n,w,L; cin>>n>>w>>L;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin>>v[i];

    queue<int> q;
    for(int i=0; i<w; i++) q.push(0);

    int idx = 0, sum = 0, t=0;
    while(!q.empty()) {

        sum -= q.front(); q.pop();
        if(idx < n) {
            if(sum + v[idx] <= L) {
                sum += v[idx];
                q.push(v[idx++]);
            }else q.push(0);
        }
        t++;
    }
    cout<<t;
}

'Algorithm' 카테고리의 다른 글

[BOJ] 늑대와 올바른 단어 13022번 C++  (0) 2025.05.12
[BOJ] 회전하는 큐 1021번 C++  (0) 2025.04.30
[BOJ] 줄서기 17178번 C++  (0) 2025.04.09
[BOJ] 옥상 정원 꾸미기 6198번 C++  (0) 2025.04.09
[BOJ] 포스택 25556번 C++  (0) 2025.04.08
'Algorithm' 카테고리의 다른 글
  • [BOJ] 늑대와 올바른 단어 13022번 C++
  • [BOJ] 회전하는 큐 1021번 C++
  • [BOJ] 줄서기 17178번 C++
  • [BOJ] 옥상 정원 꾸미기 6198번 C++
따봉치치
따봉치치
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BOJ
  • dp
  • typescript
  • BFS
  • 백준
  • 탐욕 알고리즘
  • Stack
  • 스택
  • 자바스크립트
  • 그리디
  • 그래프 탐색
  • 백트래킹
  • TOPCIT
  • 문자열
  • 알고리즘
  • Fe
  • 리액트
  • Greedy
  • javascript
  • 자료구조
  • 우선순위 큐
  • C++
  • 모던 리액트 딥다이브
  • 투 포인터
  • 모던 자바스크립트 딥다이브
  • 완전탐색
  • 데이터베이스
  • 누적합
  • react
  • CS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 트럭 13335번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.