트럭 - ACM 2016 문제 중에서

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

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

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

입력
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 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번째 트럭의 무게를 나타낸다.

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

샘플 1.

4 2 10
7 4 5 6
8

샘플 2.

1 100 100
10
101

샘플 3.

10 100 100
10 10 10 10 10 10 10 10 10 10
110
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

1개의 풀이가 있습니다.

루비와 대조되는 하드코딩 버젼

JavaScript

class Truck {
    constructor(weight, location) {
        this.weight = (weight || 1);
        this.location = (location || 0);
    }
    Move(dist) {
        this.location += dist;
    }
}
class myArray extends Array {
    constructor() {
        super();
    }
    RemoveByIndex(index) {
        if (index >= 0 && index < this.length)
            return this.splice(index, 1);
    }
}
class Bridge {
    constructor(length, maxWeight) {
        this.length = length;
        this.maxWeight = maxWeight;
        this.arr = new myArray();
    }
    CalcAllWeight() {
        var sum = 0;
        for (var obj of this.arr)
            sum += obj.weight;
        return sum;
    }
    CheckEntry(nextObj) {
        if (nextObj.weight > this.maxWeight)
            return "overweight";
        if (this.CalcAllWeight() + nextObj.weight > this.maxWeight)
            return false;
        return true;
    }
    In(obj) {
        this.arr.push(obj);
    }
    Out() {
        return this.arr.RemoveByIndex(0);
    }
}
class EntrySimulator {
    constructor() {
        this.bridge = new Bridge();
        this.trucks = new myArray();
    }
    SetOptions(w, L) { //w는 길이, L은 최대하중
        this.bridge = new Bridge(w, L);
    }
    SetTrucks(arr) {
        for (var i = 0; i < arr.length; i++) {
            this.trucks.push(new Truck(parseInt(arr[i]), i));
        }
    }
    Calculate() {
        var timediff = 0,
            passed = 0,
            entered = 0,
            error = undefined;
        while(!error && passed < this.trucks.length) { //이 while문을 한번 돌 때마다 한 턴(unit time)이 지나감.
            timediff++;
            for (var i = passed; i < entered; i++) { //다리 위에 올라와있는 트럭들이 먼저 이동함.
                this.trucks[i].Move(-1);
            }
            if (this.trucks[passed].location < -this.bridge.length) {
                this.bridge.Out(); //다리 위의 제일 앞 트럭이 통과했다면 관련 처리를 함.
                passed++;
            }
            if (entered >= this.trucks.length) //다리에 진입하지 못한 트럭이 더 없다면 뒷부분은 거칠 필요 없음.
                continue;
            switch (this.bridge.CheckEntry(this.trucks[entered])) { //다리 앞에 있는 트럭이 다리로 올라올 수 있는지 검사.
                case true :
                    this.bridge.In(this.trucks[entered]);
                    for (var i = entered; i < this.trucks.length; i++) { //다리 앞의 트럭이 올라왔으므로 그 트럭과 뒤의 모든 트럭들이 한칸씩 이동함.
                        this.trucks[i].Move(-1);
                    }
                    entered++;
                    break;
                case "overweight" : //입력 단계에서 걸러지지만 언젠가 있을 오류를 대비하여 작성.
                    error = true;
                    alert("초과중량 차량이 있습니다. 현재 초과중량 차량에 대한 대응 메뉴얼이 없습니다.");
                    break;
            }
        }
        return timediff;
    }
}
function FilteringResult(plain, num) { //num을 입력하지 않으면 갯수제한 없이 전부 반환함.
    var arr = plain.split(' ', num); //띄워쓰기를 기준으로 문자열을 나눔. num보다 갯수가 많으면 그 뒤는 버려짐.
    if (arr.length == 1)
        arr = arr.split(',', num); //띄워쓰기가 아니라면 쉼표를 기준으로 나눔.
    console.log(arr);
    for (var i = 0; i < arr.length; i++) {
        arr[i] = arr[i].replace(/[^0-9]/g,''); //각 문자열에서 숫자를 제외하고 모두 제거.
    }
    console.log(arr);
    return arr;
}
function Simulate() {
    var simulator = new EntrySimulator();
    var truck_num = 1, bridge_length, bridge_limit;
    const MIN_NUM = 1, MAX_NUM = 1000,
          MIN_LEN = 1, MAX_LEN = 100,
          MIN_WTL = 10, MAX_WTL = 1000;
    while (true) {
        var result = FilteringResult(prompt("Set number of trucks(1 ~ 1000), bridge length(1 ~ 100), bridge max weight(10 ~ 1000). use space or comma as separator.", "4 2 10"), 3);
        truck_num = result[0];
        bridge_length = result[1];
        bridge_limit = result[2];
        if (truck_num < MIN_NUM) {
            alert("트럭이 최소 한 대는 있어야 합니다"); //제한에 걸리지 않을 때까지 계속 입력을 반복함.
            continue;
        }
        if (truck_num > MAX_NUM) {
            alert("트럭의 갯수가 너무 많습니다");
            continue;
        }
        if (bridge_length < MIN_LEN) {
            alert("다리의 길이가 너무 짧습니다.");
            continue;
        }
        if (bridge_length > MAX_LEN) {
            alert("다리의 길이가 너무 깁니다.");
            continue;
        }
        if (bridge_limit < MIN_WTL) {
            alert("최대 하중이 너무 작습니다.");
            continue;
        }
        if (bridge_limit > MAX_WTL) {
            alert("최대 하중이 너무 큽니다.");
            continue;
        }
        break; //어떤 제한에도 걸리지 않으면 통과.
    }
    simulator.SetOptions(bridge_length, bridge_limit);
    var trucks;
    const MIN_TW = 1, MAX_TW = 10;
    while(true) {
        var result = FilteringResult(prompt("Input weight of each trucks(1 ~ 10)", "7 4 5 6"), truck_num);
        var error = false;
        for (var i = 0; i < result.length; i++) {
            result[i] = parseInt(result[i]);
            if (result[i] < MIN_TW) {
                alert("트럭의 무게가 너무 작습니다.");
                error = true;
                break;
            }
            if (result[i] > MAX_TW) {
                alert("트럭의 무게가 너무 큽니다.");
                error = true;
                break;
            }
        }
        if (!error)
            break;
    }
    simulator.SetTrucks(result);
    alert("Result : " + simulator.Calculate() + " unit time");
}
window.addEventListener('load', Simulate);

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 15
java x 3
python x 5
javascript x 1
기 타 x 2
cpp x 3
ruby x 1