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

권용훈

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

2개의 풀이가 있습니다.

다리로 이용할 리스트(길이가 w 이고 0으로 가득찬)를 준비해서 큐로 사용합니다. 다리의 내용을 한 칸 밀고, 남은 무게의 합과 대기열 중 가장 앞 트럭의 무게를 더해서 안전한 수준이면 다리 뒤에 추가합니다. 그렇지 않으면 0을 추가합니다. 대기열에 트럭이 없는 경우에도 다리는 0을 밀어넣습니다.

이런식으로 트럭대기열이 비고, 다리위에 트럭이 없을 때까지 반복해서 몇 번 반복했는지 카운트를 세면 됩니다.

(수정)

다리를 못 건너는 트럭이 있을 수 있어서 체크하는 로직을 추가했습니다. 더불어 각 틱마다 트럭의 위치를 표시하게끔 했습니다.

def do():

    n, w, l = [int(x) for x in input().split()][:3]
    xs = [int(x) for x in input().split()][:n]
    if max(xs) > l:
        print("can't cross the bridge.")
    bridge = [0] * w
    elapsed = 0

    def show():
        print(
            elapsed,
            '({:02d})'.format(sum(bridge)),
            ''.join('[{}]'.format(x if x > 0 else '_') for x in bridge),
            xs
        )

    show()
    while xs or sum(bridge) > 0:
        x = xs[0] if xs else 0
        if sum(bridge[1:]) + x <= l:
            bridge = bridge[1:] + [x]
            xs = xs[1:]
        else:
            bridge = bridge[1:] + [0]
        elapsed += 1
        show()
    return elapsed

print(do())

아래는 결과입니다

8 4 12
4 2 5 8 6 2 4 9
(00) (00) [_][_][_][_] [4, 2, 5, 8, 6, 2, 4, 9]
(01) (04) [_][_][_][4] [2, 5, 8, 6, 2, 4, 9]
(02) (06) [_][_][4][2] [5, 8, 6, 2, 4, 9]
(03) (11) [_][4][2][5] [8, 6, 2, 4, 9]
(04) (11) [4][2][5][_] [8, 6, 2, 4, 9]
(05) (07) [2][5][_][_] [8, 6, 2, 4, 9]
(06) (05) [5][_][_][_] [8, 6, 2, 4, 9]
(07) (08) [_][_][_][8] [6, 2, 4, 9]
(08) (08) [_][_][8][_] [6, 2, 4, 9]
(09) (08) [_][8][_][_] [6, 2, 4, 9]
(10) (08) [8][_][_][_] [6, 2, 4, 9]
(11) (06) [_][_][_][6] [2, 4, 9]
(12) (08) [_][_][6][2] [4, 9]
(13) (12) [_][6][2][4] [9]
(14) (12) [6][2][4][_] [9]
(15) (06) [2][4][_][_] [9]
(16) (04) [4][_][_][_] [9]
(17) (09) [_][_][_][9] []
(18) (09) [_][_][9][_] []
(19) (09) [_][9][_][_] []
(20) (09) [9][_][_][_] []
(21) (00) [_][_][_][_] []

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

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

풀이 작성

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

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


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