[ 백준 ] 13335 / 트럭

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
141/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 13335 / 트럭
 *
 * Kind :: Simulation
 *
 * Insight
 * - 주어지는 트럭들의 순서대로 다리를 건너야 한다
 *   + 주어지는 트럭들의 순서대로 건네줄 자료구조가 필요하다
 *     # Queue 를 사용하자
 *   다리는 다리를 건너길 시작하는 트럭들을 넣어주고 다리를 다 건넌 트럭들을 빼주어야 한다
 *   + 뒤에서 트럭을 넣어주고 앞에서 트럭을 빼줄 자료구조가 필요하다
 *     # Deque 을 사용하자
 *
 * Point
 * - 생각해 볼 점들
 *   + 다리를 건너길 시작한 트럭들을 다리위에 놓아줄 때,
 *     초기 이동한 단위길이를 0 으로 할 것인가? 1 로 할 것인가?
 *   + 다리를 건너길 시작하는 트럭을 넣어주는 작업을 먼저할 것인가,
 *     다리를 다 건넌 트럭을 빼주는 작업을 먼저할 것인가?
 *   + 다리 위 트럭들의 무게 총합을 언제 갱신시켜 줄 것인가?
 *   + 다리 위에 있는 트럭들의 움직임을 어떻게 추적할 것인가?
 *   + 모든 트럭이 다리를 건넌 것을 어떻게 확인할 것인가?
 *   + 시간은 언제 증가시켜줄 것인가?
 *   + 다리의 단위길이가 w 일때, 
 *     트럭이 w 단위길이만큼 움직였을 때 다리를 건넌 것으로 봐야할까?
 *     아니면 w+1 단위길이만큼 움직였을 때 다리를 건넌 것으로 봐야할까?
 *     # 정답은 없다, 각자의 논리에 따른 구현에 있어서 위와 같은 점들이 조금씩 달라지기에
 *
 * - 저는...
 *   + 일단 다리위 트럭들의 무게 합을 쉽게 다루기 위해
 *     다리를 다 건넌 트럭들을 먼저 빼줘서 다리의 무게를 줄여주고
 *     그 다음 대기중인 트럭들을 넣어서 다리의 무게를 늘리는 방향으로 구현했다
 *   + 다리를 건너길 시작한 트럭들의 초기 이동한 단위길이는 0 으로 설정한 후,
 *     트럭을 넣고 빼준뒤에, 다리 위 트럭들의 건넌 단위길이를 1 증가시켜주었다
 *   + Truck 이라는 구조체를 선언해서 트럭의 무게와 건넌 단위길이를 추적했다
 *   + 대기중인 트럭과 다리위 트럭이 없으면 트럭 모두가 다리를 건넌것으로 간주했다
 *   + 트럭 모두가 다리를 건너지 않았으면 시간을 1초 증가시켰다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>
#include <deque>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Truck { int w, d; }; /* w - 트럭의 무게, d - 트럭이 다리위에서 움직인 단위길이 */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, W, L;
    cin >> N >> W >> L;
    queue<Truck> waiting; /* 대기중인 트럭들을 담은 Queue */
    for (int i=0; i<N; i++) {
        int w; cin >> w;
        waiting.push({w, 0});
    }

    // Process
    deque<Truck> bridge; /* 다리 위에 있는 트럭들을 담은 Deque */
    int bw = 0; /* 현재 다리 위의 무게 */

    int time = 0; /* 시간 카운터 */
    /* 대기중인 트럭과 다리위의 트럭이 모두 비어있지 않으면
     * 즉, 트럭들이 모두 다리를 건너지 않았으면 */
    while (not(waiting.empty() && bridge.empty())) {
        /* 시간 증가 */
        time++;

        /* 다 건넌 트럭 다리위에서 빼주기 */
        if (not(bridge.empty())) {
            Truck t = bridge.front(); /* 다리를 가장 많이 건넌 트럭 */
            if (t.d == W) { /* 위의 트럭이 다리를 다 건넜다면 */
                bridge.pop_front(); /* 다리에서 빼줌 */
                bw -= t.w; /* 다리의 현재 무게 갱신 */
            }
        }

        /* 건너길 시작한 트럭 다리위에 넣어주기 */
        if (not(waiting.empty())) {
            Truck t = waiting.front(); /* 대기중인 트럭 중 첫번째 트럭 */
            if (bw + t.w <= L) { /* 현재 다리의 무게 + 위의 트럭의 무게 <= 최대하중 이면 */
                bridge.push_back(t); /* 다리에 넣어줌 */
                waiting.pop(); /* 대기열에서는 빼줌 */
                bw += t.w; /* 다리의 현재 무게 갱신 */
            }
        }

        /* 매 단위시간마다, 다리 위에 있는 모든 트럭들이 1 단위길이 만큼 이동 */
        for (Truck &t : bridge) {
            t.d++;
        }
    }

    // Control : Output
    cout << time << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글