Programming Challenges #29

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

입력

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

function findMinimumPenalty(testCases) {
  const results = [];

  for (let i = 0; i < testCases.length; i++) {
    const testCase = testCases[i];
    const N = testCase.length;
    const jobs = [];

    for (let j = 0; j < N; j++) {
      const [T, S] = testCase[j];
      jobs.push([T, S]);
    }

    // 작업을 벌금 기준으로 오름차순 정렬
    jobs.sort((a, b) => a[1] - b[1]);

    let totalPenalty = 0;
    let delay = 0;

    for (let j = 0; j < N; j++) {
      const [T, S] = jobs[j];
      delay += T;
      totalPenalty += delay * S;
    }

    results.push(totalPenalty);
  }

  return results;
}

// 입력값
const input = [
  [
    [[3, 4], [1, 1], [4, 100]],
    [[1, 1], [2, 2], [3, 3], [4, 4]]
  ]
];

// 결과 출력
const output = findMinimumPenalty(input);
for (let i = 0; i < output.length; i++) {
  console.log(output[i]);
}

예시: 입력: 

3

3 4

1 1

4 100

4

1 1

2 2

3 3

4 4

출력: 104 10

해설:

첫 번째 테스트 케이스에서 작업을 2-1-3 순서로 처리하면 벌금의 총합은 (3x4) + (1x1) + (4x100) = 104가 된다.

두 번째 테스트 케이스에서 작업을 4-3-2-1 순서로 처리하면 벌금의 총합은 (4x4) + (3x3) + (2x2) + (1x1) = 10이 된다.