트럭 - 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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

3개의 풀이가 있습니다.

Java

  • 트럭 클래스를 정의하고 다리 최초 진입 시의 진행 단계(stage)와 다리를 다 건넜을 때의 단계를 기록한다.
  • 트럭은 한 번 다리에 올라가면 다리 길이 만큼 진행 후에 다리를 건넌 상태가 된다.
  • 제일 마지막으로 지나간 트럭의 종료 단계를 출력한다.
import java.util.Scanner;

public class TruckTimer {
    public static int process(String input1, String input2) {
        String[] inputList1 = input1.split(" ");
        String[] inputList2 = input2.split(" ");
        int w = Integer.parseInt(inputList1[1]);
        int l = Integer.parseInt(inputList1[2]);
        Truck[] trucks = new Truck[inputList2.length];
        for (int i = 0; i < trucks.length; i++) {
            int weight = Integer.parseInt(inputList2[i]);
            trucks[i] = new Truck(weight);
        }
        return checkTime(w, l, trucks);
    }

    private static int checkTime(int w, int l, Truck[] trucks) {
        int stage = 1;
        int currentWeight = 0;
        for (int i = 0; i < trucks.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (trucks[j].endStage == stage) {
                    currentWeight -= trucks[j].weight;
                }
            }
            if (currentWeight + trucks[i].weight <= l) {
                currentWeight += trucks[i].weight;
                trucks[i].startStage = stage;
                trucks[i].endStage = stage + w;
                stage++;
            } else {
                stage += w;
                trucks[i].startStage = stage;
                trucks[i].endStage = stage + w;
            }
        }
        return trucks[trucks.length-1].endStage;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input1 = sc.nextLine();
        String input2 = sc.nextLine();
        System.out.println(TruckTimer.process(input1, input2));
    }
}

class Truck {
    public final int weight;
    public int startStage;
    public int endStage;
    public Truck(int weight) {
        super();
        this.weight = weight;
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

JAVA

Truck, Bridge 클래스를 만들었습니다. Truck 자신의 위치를 알고 있습니다. Bridge 클래스는 현재 건너고 있는 트럭들을 리스트로 갖습니다. 리스트에 있는 트럭을 한 번에 시행에서 모두 왼쪽으로 이동합니다. 저는 W값에서 0으로 이동하면 다 이동했다고 판단하여 그 트럭을 리스트에서 제거 시킵니다. 트럭을 추가할 때는 현재 새로 들어올 트럭이 totalWeight에 포함이 되어도 최대 하중을 버틸 수 있는지 체크를 합니다. 버틸 수 있다면 리스트에 추가를 합니다. main 함수에는 모든 트럭이 추가됐는지 또는 모든 트럭이 다리를 지나갔는지 두 가지를 판단하여 while 문을 돌립니다.

Truck 트럭 클래스

public static class Truck {
        private int weight;
        private int position;

        public Truck(int position, int weight) {
            this.position = position;
            this.weight = weight;
        }

        public void decraese() {
            this.position--;
        }

        public int getPosition() {
            return this.position;
        }
        public int getWeight() {
            return weight;
        }
    }

Bridge 클래스

public static class Bridge {
        private int W;
        private int L;
        private ArrayList<Truck> trucks;
        int totalWeight = 0;
        public Bridge(int w, int l) {
            W = w;
            L = l;
            trucks = new ArrayList<>();
        }

        public void moveLeft() {
            Truck removed = null;
            if (trucks == null) {
                return;
            }
            if (trucks.size() < 1) {
                return;
            }
            for (Truck truck : trucks) {
                truck.decraese();
                if(truck.getPosition() < 1) {
                    totalWeight -= truck.getWeight();
                    removed = truck;
                }
            }
            if (removed != null) {
                trucks.remove(removed); 
            }
        }
        public int trucksSize() {
            return trucks.size();
        }
        public void enterTruck(Truck truck) {
            totalWeight += truck.getWeight();
            trucks.add(truck);
        }
        public boolean ableEnterTruck(int weight) {
            if (totalWeight + weight <= L && trucks.size() < W) {
                return true;
            } else {
                return false;
            }
        }
    }

Main 클래스


public class TruckACM2016 {

    static final int SIZE = 1000;
    static int n, w, l;


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = getInput(args);

        int i=0;
        int count =0;
        Bridge bridge = new Bridge(w, l);
        Truck truck;
        while(i<n || bridge.trucksSize() > 0) {
            bridge.moveLeft();
            if (i<n && bridge.ableEnterTruck(A[i])) {
                truck = new Truck(w, A[i]);
                bridge.enterTruck(truck);
                i++;
            }
            count++;
        }
        System.out.println("count : "+count);

    }

    public static int[] getInput(String[] args) {
        int i = 0;
        int[] input = new int[SIZE];
        n = Integer.valueOf(args[i++]);
        w = Integer.valueOf(args[i++]);
        l = Integer.valueOf(args[i++]);
        for (; i<n+3; i++) {
            input[i-3] = Integer.valueOf(args[i]);
        }
        return input;
    }

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

트럭마다 다리에 들어오는 시간과 나가는 시간을 계산합니다.
한 트럭이 다리에 들어오는 시간은
(자기포함 앞쪽의 트럭의 무게를 합산해나가다가 하중을 넘치는 트럭의 나가는 시간) 과
(내 직전 트럭의 다리에 들어오는 시간 + 1 ) 중
큰 값이 됩니다.
트럭이 다리에서 나가는 시간은 (들어오는 시간 + 다리의 길이) 입니다.
입력받으면서 순차 계산하고 맨 마지막 트럭의 나가는 시간이 답이 됩니다.

최악의 경우 O(NlogN) 으로 풀리며, 최선의 케이스는 O(N) 으로 해결됩니다.

ex) 입력이 다음과 같을 경우
4 2 10
7 4 5 6
List배열은 아래와 같이 채워집니다.
7 1 3
4 3 5 (무게가 넘치는 트럭의 나가는 시간 3, 직전 트럭의 들어가는 시간+1 은 2) -> 3
5 4 6 (무게가 넘치는 트럭의 나가는 시간 3, 직전 트럭의 들어가는 시간+1 은 4) -> 4
6 6 8 (무게가 넘치는 트럭의 나가는 시간 6, 직전 트럭의 들어가는 시간+1 은 5) -> 6

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class A39TruckBridge {

    static StringTokenizer st;
    static int N;   //트럭갯수
    static int L;   //다리길이
    static int W;   //최대하중
    static int [][] List;
    static int sumWeight;
    static int lastTime;

    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer (br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        List = new int [N][3];  // 0컬럼은 트럭무게, 1컬럼은 다리에 들어서는 시간, 2컬럼은 다리를 빠져나가는 시간

                // 첫번째 트럭의 값을 입력
        st = new StringTokenizer (br.readLine());
        List[0][0] = Integer.parseInt(st.nextToken());
        List[0][1] = 1;
        List[0][2] = List[0][1] + L;

        for (int i=1; i<N; i++) {
            List[i][0] = Integer.parseInt(st.nextToken());

            sumWeight = List[i][0];

            for (int x = i-1; x >= 0; x--) {
                sumWeight += List[x][0];
                lastTime = List[x][2];
                if (sumWeight > W) break;
            }
            List[i][1] = Math.max(List[i-1][1]+1, lastTime);
            List[i][2] = List[i][1] + L;
        }
        System.out.println(List[N-1][2]);
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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


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