백준 2109 순회강연 (그리디)

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

제한 사항

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const sol = (input) => {
  const n = +input.shift();
  if (n === 0) {
    return 0;
  }
  const table = input.map((e) => e.split(" ").map(Number));
  
  // 비용 내림차순으로 정렬
  table.sort((a, b) => {
    return b[0] - a[0];
  });
	
  // 스케쥴 확인용
  const visited = new Array(10001).fill(0);
  let sum = 0;
  for (let i = 0; i < n; i++) {
    for (let j = table[i][1]; j > 0; j--) {
      if (!visited[j]) {
        sum += table[i][0];
        visited[j] = 1;
        break;
      }
    }
  }
  return sum;
};

console.log(sol(input));

직관적으로 비용이 큰 순서대로 내림차순 정렬하면 되겠다 생각 할 수 있다. 하지만, d일 이내의 강연을 선택하는 것이지 d일째만 강연을 선택하는 것이 아니기 때문에 추가적인 탐색이 필요하다.

비용이 큰 순으로 정렬하고 그 비용에 해당하는 날짜를 역순으로 1일까지 스케쥴(visited)을 확인한다. 해당 스케줄이 비어있다면! 방문처리를 해주고 sum에 값을 누적해준다. 그리고 반드시 break를 해줘야한다.

문제를 예로들어 table을 비용순으로 정렬하면,
100 2
50 10
20 1
10 3
8 2
5 20
2 1
의 결과가 나온다.

처음 비용은 100이고 2일차, 반복문을 통해 2일차를 방문처리하고 100을 sum에 누적할 것이다. 여기서 break를 안하면 1일차도 방문처리되고 100이 또 추가 될 것이다. 이러한 이유때문에 하루 방문처리가 되면 바로 break해줘야 하는 것이다.

2일차에 100,
10일차에 50,
1일차에 20,
3일차에 10,
(여기가 포인트)
2일차에 8 => 이미 방문처리되어있으니 x,
차수를 줄여 1일차에 8 => 역시 방문처리되어있으니, x
(건너띄어진것)
20일차에 5,
1일차에 1 => 방문처리되어있으니 x

이런 과정으로 185가 되는 것이다.