트럭 - 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

2016/10/11 20:59

권용훈

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

22개의 풀이가 있습니다. 1 / 3 Page

w, L = 2, 10
trucks = [7, 4, 5, 6]
bridge = [0] * w

i = 0
while sum(bridge + trucks) > 0:
    bridge.pop(0)
    n = trucks.pop(0) if trucks and sum(bridge) + trucks[0] <= L else 0
    bridge += [n]
    i += 1
    print(i, bridge, trucks)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python3

def cross(W, L, trucks):
    bridge = [0] * W
    time = 0
    while bridge:
        time += 1
        bridge.pop(0)
        if trucks:
           if sum(bridge) + trucks[0] <= L:
               bridge.append(trucks.pop(0))
           else:
               bridge.append(0)

        #print(bridge); input()

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

경우의 수를 다 뒤져봐야하는 NP-완전문제 -> greedy로 푸는게 나을듯 가장 빠른 시간내에 통과한다는 조건 -> 모든 차가 지나가는 배열에 공백이 없이 최대한 채움 -> 윈도우 내에 최대한 무게를 꽉꽉 채움

def calc_fast_time(w, l, cars_l):
    passing_arr = []
    cars_l_sorted = list(reversed(sorted(cars_l)))
    t = 0
    while cars_l_sorted:
        window = passing_arr[-w+1:] # 1대씩 추가할 거니까 배열의 마지막 w-1개까지만 가져옴

        # 윈도우 내의 남은 무게
        win_l = sum(window)
        rest_l = l - win_l

        # 해당 위치에 들어갈 차를 선택
        for car in cars_l_sorted:
            if car <= rest_l:
                passing_arr.append(car)
                cars_l_sorted.remove(car)
                t += 1
                break
        # 채울 수 있는 무게가 모자르면 공백을 채움
        if cars_l_sorted and (rest_l == 0 or rest_l < min(cars_l_sorted)):
            passing_arr.append(0)
            t += 1
    print('elapsed:', t+w) #마지막 차까지 사라지려면 다리가 마지막차가 w만큼 시간이 더 든다

# w l arr
calc_fast_time(2, 10, [7, 4, 5, 6])

# w l arr
calc_fast_time(100, 100, [10])

# w l arr
calc_fast_time(100, 100, [10 for x in range(10)])

결과

elapsed: 8
elapsed: 101
elapsed: 110
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import static java.lang.System.in;

public class Truck {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int l = sc.nextInt();
        for (int i = 0; i < n; i++) {
            ((List<Integer>) new ArrayList(n)).add(sc.nextInt());
        }

        ((List<Integer>) new ArrayList(n)).stream().reduce((a, b) -> {
            if (a + b > l) ((List<Integer>) new ArrayList(n)).add(w - 1);
            return b;
        });

        System.out.println(n + w + ((List<Integer>) new ArrayList(n)).stream().mapToInt(Integer::intValue).sum());
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

move 라는 method를 구현해서, bridge list 와 트럭 list가 한 칸씩 움직일 때마다 사용하는 방법으로 풀어봤습니다. 초보라서 input 받는 부분이 복잡하네요ㅠ

#x = input("input n, w, L and a_n with new line.")
#x = '4 2 10\n7 4 5 6'
#x = '1 100 100\n10'
x ='10 100 100\n10 10 10 10 10 10 10 10 10 10'

def move(list):
    for i in range(len(list)- 1):
            list[i] = list[i+1]
    list[-1] = 0

t = 1
x = x.split('\n')
n, w, L = x[0].split(' ')
a = x[1].split(' ')
a = [int(i) for i in a]
bridge = [0] * int(w)
bridge[-1] = a[0]
move(a)

while 1:
    t += 1
    bridge[0] = 0

    if sum(bridge) + sum(a) == 0:
        break

    elif sum(bridge) + a[0] <= int(L):
        move(bridge)
        bridge[-1] = a[0]
        move(a)

    else:
        move(bridge)

print(t)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def count_up(val):
    return val+1

data = list(map(int,input().split(' ')))
bus = list(map(int,input().split(' ')))
count, length, weight = 0,0,0
bus2, gps = list(), list()

while bus != [] or bus2 != []:
    count += 1
    if gps != []:
        gps = list(map(count_up,gps))
        if gps[0] == data[1]:
            weight -= bus2.pop(0)
            length -= 1
            gps.pop(0)
    if bus != [] and weight+bus[0] <= data[2] and length < data[1]:
        weight += bus[0]
        length += 1
        gps.append(0)
        bus2.append(bus.pop(0))
print(count)

#### 2017.01.24 D-394 ####
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def bridgetruck(*args):
    x=[list(map(lambda x: int(x), arg.split(" "))) for arg in args]
    a=x[1]; n=x[0][0]; w=x[0][1]; l=x[0][2]; bridge=[0]*w; time=0
    while sum(a)>0:
        if a[0]>w: return "이 화물로는 도저히 다리를 건널 수 없겠는걸?"
        time+=1; bridge.pop(0)
        if sum(bridge)+a[0] < l:
            bridge.append(a.pop(0))
        else: bridge.append(0)
    return time+w

ss=input("다리 정보:" )
sa=input("화물트럭 정보: ")
print(bridgetruck(ss, sa))

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

C로작성

부족한 부분이나 개선점은 지적 부탁드려용

#include <stdio.h>

int main(){

    int truck_n = 0, Bridge_w = 0, Weight_L = 0;
    int a[100] = {0,};
    int i = 0, j =0, temp = 0;
    int ans = 0;
    int status = 0;

    int *Bridge_Array;

    FILE *fp;
    fp = fopen("input_1.txt","rt");
    if(fp == NULL){
        printf("파일 읽기 실패\r\n");
        system("pause");
        return 1;
    }

    //트럭수, 다리길이, 다리 최대하중
    fscanf(fp, "%d %d %d", &truck_n, &Bridge_w, &Weight_L);

    //트럭 무게 읽기
    for(i = 0; i < truck_n; i++){
        fscanf(fp, "%d", &a[i]);
    }

    //다리 길이에 맞는 배열 만들기
    Bridge_Array = (int*)malloc(sizeof(int)*Bridge_w);
    for(j = 0; j < Bridge_w; j++){
        Bridge_Array[j] = 0;
    }

    //For debug
    printf("트럭갯수 : %d, 다리 길이 : %d, 최대 하중 : %d \r\n", truck_n, Bridge_w, Weight_L);

    printf("각 트럭 무게 : "); 
    for(i = 0; i<truck_n; i++){
        printf("%d ", a[i]);
    }
    printf("\r\n"); 
    //////


    i = 0;
    j = 0;
    status = Bridge_w;

    while(1){

        int sum_Weight = 0;
        int k = 0;


        if(i == truck_n){   //마지막 트럭이 출발함
            status --;
        }else{                      //아직 가야할 트럭 남음

            //다리 마지막 위치를 제외한 위치의 무게 SUM
            for(k=0; k<(Bridge_w-1); k++){
                sum_Weight += Bridge_Array[k];
            }
            //+새로운 트럭 무게 
            sum_Weight += a[i];
        }

        //트럭 이동
        for(k=Bridge_w - 1; k != 0; k--){
            Bridge_Array[k] = Bridge_Array[k-1];
        }

        //최대 하중을 넘지 않고, 가야할 트럭이 남아있으면,
        if((sum_Weight <= Weight_L) && (i < truck_n)){

                //새 트럭 출발
                Bridge_Array[0] = a[i];
                i++;

        }else{

            //무게 0 대입
            Bridge_Array[0] = 0;
        }

        //For debug Start
        /*
        for(j = 0; j<Bridge_w; j++){
            printf("%d ", Bridge_Array[j] ); 
        }
        printf("\r\n"); 
        */
        //For debug End

        ans++;

        if(status == 0){
            break;
        }
    }

    printf("ans : %d \r\n", ans); 
    fclose(fp);

    system("pause");

    return 0;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
a=input().split(" ")
b=input().split(" ")
if int(a[0])==len(b):
    w=list()
    r=0
    t=0
    for i in range(int(a[1])):
        w.append(0)
    while 1:
        if b.count(0)==len(b) and sum(w)==0:
            break
        if r<int(a[1]):
            w.pop(0)
            if sum(w)+int(b[0])<=int(a[2]):
                w.append(int(b[0]))
                b.pop(0)
                b.append(0)
                t=t+1
                r=r+1
            else:
                w.append(0)
                t=t+1
                r=r+1
        else:
            r=0

    print(t)
else:
    print("잘못된 입력입니다.")
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
n, w, L = map(int, input(":").strip().split(' '))
an = list(map(int, input(":").strip().split(' ')[:n]))
q = [0] * w
t = 0
for i in an:
    while True:
        t+=1
        q.pop(0)
        if i > L:
            raise Exception('ai <= L')
        elif sum(q)+i > L:
            q.append(0)
        else:
            q.append(i)
            break
while sum(q) != 0:
    t+=1
    q.pop(0)
print(t)

Python 3.5.2에서 작성하였습니다.

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

풀이 작성

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

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


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