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

20개의 풀이가 있습니다. 1 / 2 Page

경우의 수를 다 뒤져봐야하는 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에서 작성하였습니다.

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

트럭마다 다리에 들어오는 시간과 나가는 시간을 계산합니다.
한 트럭이 다리에 들어오는 시간은
(자기포함 앞쪽의 트럭의 무게를 합산해나가다가 하중을 넘치는 트럭의 나가는 시간) 과
(내 직전 트럭의 다리에 들어오는 시간 + 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]);
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <stdio.h>

typedef struct TRUCK
{
    int nWeight;  //트럭의 무게
    int nTime;    //다리 통과 까지 남은 시간
    bool bPass;   //통과 했나
    bool bStart;  //시작 했나
}TRUCK;

int main(int argc, char argv[])
{
    TRUCK sTruck[1000];      //n
    int nNumberOfTruck = 0;
    int nBridgeLength = 0;   //w
    int nMaxWeight = 0;      //L
    int i = 0;
    //input
    scanf("%d %d %d", &nNumberOfTruck, &nBridgeLength, &nMaxWeight);
    for(i = 0; i < nNumberOfTruck; i++)
    {
        scanf("%d", &sTruck[i].nWeight);
        sTruck[i].nTime = nBridgeLength;
        sTruck[i].bPass = false;
        sTruck[i].bStart = false;
    }

    //input data check
    printf("Number of Truck(n): %d\n", nNumberOfTruck);
    printf("Bridge Length(w): %d\n", nBridgeLength);
    printf("Bridge Maximum Weight(L): %d\n", nMaxWeight);
    printf("Truck Weight(a_n)\n");
    for(int i = 0; i < nNumberOfTruck; i++)
        printf("%d ", sTruck[i]);
    printf("\n\n");

    //check done

    //start
    int nNowBridgeTruckWeight = 0; //다리 위에 올라와 있는 트럭의 무게
    int nTruckPos = 0; // 트럭 위치
    int nTime = 0;
    while(1)
    {
        //모든 트럭이 다 건넜나? 마지막 트럭만 체크를 해 준다.
        if(sTruck[nNumberOfTruck-1].bPass == true)
            break;

        //단위 시간 증가
        nTime++;
        //printf("now Time: %d\n", nTime);

        //다리에 올라와 있는 트럭들 이동
        for(i = 0; i < nNumberOfTruck; i++)
        {
            //트럭이 출발했고 && 아직 다리를 건너지 못했다면
            if(sTruck[i].bStart == true && sTruck[i].bPass == false)
            {
                //트럭이 다리를 건너기 까지 남은 시간의 감소
                sTruck[i].nTime--;
                //printf("%d트럭 남은 시간: %d\n",i,  sTruck[i].nTime);
            }
        }

        //다리를 건넌 트럭이 있는지 확인한다.
        for(i = 0; i < nTruckPos; i++)
        {
            if(sTruck[i].nTime <= 0 && sTruck[i].bPass == false)
            {
                //다리 건넌 표시를 해준다.
                sTruck[i].bPass = true;

                //다리를 다 건넜으니 다리에 가해지고 있던 하중을 빼 준다.
                nNowBridgeTruckWeight -= sTruck[i].nWeight;

                //printf("다 건넌 트럭: %d\n", i);
            }
        }


        //최대 다리 하중보다 현재 트럭의 무게가 낮으면(이하이면) 트럭이 올라간다
        //하나의 단위시간에 하나의 트럭밖에 올라가지 못한다.
        //printf("[%d]부하 하중:%d 올라가고자 하는 트럭의 무게:%d \n", nTime, nNowBridgeTruckWeight, sTruck[nTruckPos].nWeight);
        if(sTruck[nTruckPos].bStart == false)
        {
            if((nNowBridgeTruckWeight + sTruck[nTruckPos].nWeight) <= nMaxWeight)
            {
                nNowBridgeTruckWeight += sTruck[nTruckPos].nWeight;
                sTruck[nTruckPos].bStart = true;
                //printf("%d시간 %d번 트럭 올라감. 무게 %d\n", nTime, nTruckPos, sTruck[nTruckPos].nWeight);
                nTruckPos++;
            }
        }
    }

    printf("elapsed Time: %d\n", nTime);

    return 0;
}

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

풀이 작성

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

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


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