C언어 213제] 구두 수선공 문제(Shoemaker's Problem)

출처 : 반크_백제역사 유적지구와 이스탐블역사 유적지구

 

문제]

어떤 구두 수선공에게 N개의 주문이 들어와 있다. 그는 하루에 한 가지 작업만 할 수 있으며 보통 한 작업을 하는데 며칠이 걸린다. i번째 작업에 대해 Ti(1<=Ti<=1000)라는 정수는 구두 수선공이 작업을 끝내는데 걸리는 시간이 며칠인지를 나타낸다.
하지만 인기가 좋으면 그 만큼의 대가가 따른다. 구두 수선공은 i번째 작업을 시작하기 전까지 지연되는 날 수를 기준으로 하루에 Si(1<=Si<=10000) 센트씩의 벌금을 내기로 했다. 벌금의 총합이 최소가 되게 해주는 작업 순서를 찾아내기 위한 프로그램을 만들어서 구두 수선공을 도와주자.

입력
첫 줄에는 테스트 케이스의 개수를 나타내기 위한 양의 정수 한 개가 들어가며 그 다음 줄은 빈 줄이다. 서로 다른 테스트 케이스 사이에도 빈 줄이 하나씩 들어간다.
각 케이스의 첫번째 줄에는 작업의 개수 N을 알려주는 정수가 들어있으며 이때 1<=N<=1000이다. 그 다음 줄부터 N개의 줄에 걸쳐서 작업에 대한 정보가 입력되며 i번째 작업에 대한 정보가 들어있는 줄에는 그 작업을 끝내는데 걸리는 날 수인 Ti와 하루당 벌금 Si가 입력된다.

출력
각 테스트 케이스에 대해 벌금이 최소가 되는 작업 순서를 출력한다. 각 작업은 입력된 순서를 기주으로 표시된다. 모든 정수는 한 줄에 들어있어야 하며 서로 다른 작업을 나타내는 정수 사이에는 스페이스가 한개씩 들어간다. 여러 작업 순서가 가능하다면 사전 순서를 기준으로 제일 앞에 있는 것을 출력한다. 서로 다른 케이스는 빈 줄로 구분한다.

입력 에
1

4
3 4
1 1000
2 2
5 5

출력 예
2 1 3 4

 

 

출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제 29 구두 수선공 문제(Shoemaker's Problem) p129

 

참고풀이]

#include <stdio.h>

static int N, R[1000];
static int Ti[1000], Si[1000];

void Input()
{
   int i;
   scanf("%d",&N);
   for(i=0; i<N;i++)
      scanf("%d%d",&Ti[i], &Si[i]);
}

void Solve()
{
   int i, j, tmp;
   for(i=0; i<N; i++) R[i]=i;

   //버블 정렬 
   for(i=1;i<N;i++)
      for(j=0;j<N-i;j++)
         if(Ti[R[j]]*Si[R[j+1]] > Ti[R[j+1]]*Si[R[j]])
         {
            tmp=R[j]; R[j]=R[j+1]; R[j+1]=tmp;
         }
}

int main()
{
   int i, j, t;

   scanf("%d",&t);
   for(i=0; i<t; i++)
   {
      Input();
      Solve();
      if(i>0) printf("\n");
      for(j=0;j<N-1;j++)
         printf("%d ", R[j]+1);
      printf("%d\n", R[N-1]+1);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 겨울