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

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

#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;
}

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

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

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
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("잘못된 입력입니다.")
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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

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

풀이 작성

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

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


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