트럭 - 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개의 풀이가 있습니다.

#include <cstdlib>
#include <iostream>

using namespace std;

int count_zero(int *a,int m){
     int i;
     for(i=0;i<m;i++){
                      if(a[i]!=0)return 1;
                      }
      return 0;               
}

int count_sum(int *b,int m){
      int i;
      int sum=0;
      for(i=0;i<m;i++){
                       sum=sum+b[i];
                       }
      return sum;                      
}


int  clean1(int *a,int m,int n){

     int i;

     for(i=0;i<m;i++){
                      if(a[i]==n){
                                  a[i]=0;
                                  return 0;
                                  }
                      }
     return 1;
     }


int main(int argc, char *argv[])
{
    FILE* stream1;

    int m,w,n;//m 차량수 ,w 다리길이, n 하중한계 

    int i,j;

    //int a[100]={0,};
    int *a;
    int *b;
    int z=0;
    //int b[100]={0,};
    int sum=0;

    stream1=fopen("1.txt","r");

    fscanf(stream1,"%d %d %d",&m,&w,&n);

    a=new int[m];
    b=new int[w];
    memset(a, 0, m * sizeof(int));
    memset(b, 0, w * sizeof(int));  

    for(i=0;i<m;i++){
                     fscanf(stream1,"%d",&a[i]);
                     } 

    //memset(a, 0, m * sizeof(int));
    //memset(b, 0, w * sizeof(int));          
    while(count_zero(a,m)){


                           for(i=w-1;i>=0;i--){
                                             if(b[i]!=0&&i==w-1){

                                                               // b[i+1]=b[i];
                                                                clean1(a,m,b[i]);
                                                                b[i]=0;

                                                                }



                                             if(b[i]==0&&i!=0){
                                                                  b[i]=b[i-1];
                                                                  b[i-1]=0;  
                                                                  }
                                            /*
                                            if(b[i]!=0&&i!=w-1){                                                               
                                                                //clean1(a,m,b[i]);
                                                                b[i+1]=b[i];
                                                                b[i]=0;
                                                                i--;
                                                                }
                                            */
                                            }



                           if(b[0]==0&&count_sum(b,w)+a[z]<=n){

                                                             b[0]=a[z];
                                                             //printf("%d\n",b[0]);
                                                             z++;
                                                             }                
                          /* 
                          for(i=0;i<w;i++){
                                           printf("%d ",b[i]);
                                           }
                          printf("\n");
                          /*
                          for(i=0;i<m;i++){
                                           printf("%d ",a[i]);
                                           }
                          printf("\n");                          
                           */ 
                           sum++;
                           }

    delete []a;
    delete []b;
    printf("%d\n",sum);
    system("PAUSE");
    return EXIT_SUCCESS;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

CPP code queue를 이용한 구현문제

#include <iostream> 
#include <cstdlib> 
#include <queue> 
using namespace std;  

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int N,W,L; 
    cin >> N >> W >> L;  
    int sum = 0,cnt = 0,ret = 0,truck;  
    queue<int> que; 
    for (int i = 0; i < N; i++){
        cin >> truck; 
        while (true){
            ++ret; 
            if (cnt == W){
                --cnt;  
                sum -= que.front(); 
                que.pop();  
            }
            if (sum+truck > L){
                ++cnt; 
                que.push(0);  
            }else{
                ++cnt; 
                sum += truck;  
                que.push(truck);  
                break; 
            }
        }
    }
    cout << ret+W << endl; 
    return 0; 
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#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 19
기 타 x 2
java x 4
ruby x 1
cpp x 3
javascript x 1
python x 8