브루트 포스 - 졸업 선물

문제

선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다.
학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했습니다.
선생님이 가지고 있는 예산은 한정되어 있습니다. 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요.
선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다.
배송비는 할인에 포함되지 않습니다.

 

문제 설명

▣ 입력설명
첫 번째 줄에 반 학생수 N(1<=N<=1000)과 예산 M(1<=M<=100,000,000)이 주어진다.
두 번째 줄부터 N줄에 걸쳐 각 학생들이 받고 싶은 상품의 가격과 배송비가 입력됩니다.
상품가격과 배송비는 각각 100,000을 넘지 않습니다. 상품가격은 짝수로만 입력됩니다.

 

▣ 출력설명
첫 번째 줄에 선생님이 현재 예산으로 선물할 수 있는 최대 학생수를 출력합니다.
선생님 최소한 1개 이상의 상품을 살 수 있는 예산을 가지고 있습니다.

 

▣ 입력예제 1
5 28
6 6
2 2
4 3
4 5
10 3

 

▣ 출력예제 1
4

출력설명 : (2, 2), (4, 3), (4, 5)와 (10, 3)를 할인받아 (5, 3)에 사면 비용이 4+7+9+8=28입니다.

 

---

 

먼저 해당 문제에서 요구하는 것이 무엇인지를 파악해야한다.

문제의 핵심은 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지를 구하는 것이다.

중요한 포인트는 최대 학생의 수이다.

 

🎯가장 많은 학생에게 선물을 사주기 위해서는 총 비용을 기준으로 입력값을 오름차순으로 정렬한 후에 차례대로 더해가면서 예산금액에 가장 가까우면서 최대 인원 수를 구하면 된다.

문제의 예시로 예를 들면, 총 비용을 기준으로 오름차순 정렬을 하면 다음과 같다.

2 2 - 4
4 3 - 7
4 5 - 9
6 6 - 12
10 3 - 13

 

그리고 4,7,9... 차례대로 더해가면서 인원수를 카운트하고 예산금액을 넘는 순간의 인원수를 반환하면 된다.

 

하지만,

이 문제에는 할인쿠폰이라는 옵션이 있기 때문에 조금 까다로워진다.

가장 비싼 금액의 상품을 할인한다고 해서 물건을 많이 살 수 있는 것이 아니고, 반대로 가장 싼 금액의 상품을 할인한다고 더 많은 인원에게 선물을 사줄 수 있는 것이 아니다.

때문에 인원을 순회하면서 해당 인원이 할인받을 때, 예산금액에서 최대 몇명의 인원에게 선물을 사줄 수 있는지를 구해야한다. 완전탐색을 이용해야한다.

 

우선 최대한 가장 많은 사람에게 선물을 사줘야하므로 총 비용을 기준으로 기존 배열을 오름차순 정렬한다.

 

- 1번 사람이 할인 받을 경우 최대 인원의 수
- 2번 사람이 할인 받을 경우 최대 인원의 수
...
- 5번 사람이 할인 받을 경우 최대 인원의 수

 

그리고 각각의 최대 인원수의 최댓값을 구해서 반환하면 된다.

function solution(m, arr) {
  let result = 0;
  const sorted = arr.sort(([a, b], [c, d]) => a + b - (c + d));

  for (let i = 0; i < sorted.length; i += 1) {
    let count = 1;
    let sum = sorted[i][0] / 2 + sorted[i][1];
    for (let j = 0; j < sorted.length; j += 1) {
      if (i === j) continue;

      sum += arr[j][0] + arr[j][1];
      if (sum > m) break;
      count += 1;
    }
    result = Math.max(result, count);
  }

  return result;
}

let arr = [
  [8, 6],
  [2, 2],
  [4, 3],
  [4, 5],
  [12, 1],
];
console.log(solution(41, arr));

 

브루트 포스 알고리즘은 완전 탐색이므로 각 요소들을 모두 순회하며 수행해야하는 작업들이 있는 유형으로 주로 나오는 듯 하다.

문제에서 요구하는 바를 정확하게 파악하여 이를 해결하려면 어떻게 해야하는지를 종이에 잘 적어보면서 문제해결력을 길러야겠다.