2023-10-05 알고리즘 공부 풀이

이 게시글은 인프런 알고리즘 js 강의를 듣고 공부한 내용을 정리한 게시글 입니다.

1.문제 졸업선물

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

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

2.풀이

이번 문제는 정해진 예산을 가지고 최대한 많은 학생한테 졸업선물을 줄 수 있는지를 구하는 알고리즘 문제이다.
여기서 하나 간과해야할 점은 쿠폰을 상품 한개에 적용 시킬 수 있다라는 점이다.
그렇기 때문에 우리는 어떤 물건에 쿠폰을 적용시켜야지 가장 많은 선물을 줄 수 있는지를 찾아야 한다.
완전탐색을 통해 찾아야 한다라는 점을 빠르게 catch 해야한다.

3.코드

function sol(num, arr) {
  let answer = 0;
  n = arr.length;
  arr.sort((a, b) => a[0] + a[1] - (b[0] + b[1])); //가격별로 상품을 정렬 시킴
  for (let i = 0; i < n; i++) {
    let money = num - (arr[i][0] / 2 + arr[i][1]);
    //할인은 상품에만 적용 되므로 arr[i][0] (상품가격) +배달비용을 
   // 예산에서 뺀다
    let cnt = 1;
    for (let j = 0; j < n; j++) {
      //할인된 상품을 더할 수 없기 때문에 j !=== i 조건식 만들어줌
      //money 가 상품가격보다 작아지면 break 하여 알고리즘 시간 줄임
      if (j !== i && arr[j][0] + arr[j][1] > money) break;
      if (j !== i && arr[j][0] + arr[j][1] <= money) {
        money -= arr[j][0] + arr[j][1];
        //가지고 있는 예산에다가 상품값과 배송값을 더해서 빼고 카운팅 해줌
        cnt++;
      }
    }
    answer = Math.max(answer, cnt);
    //최댓값을 비교함으로써 몇개의 물건을 살 수 있는지 찾음.
  }
  console.log(arr);
  return answer;
}
let arr = [
  [6, 6],
  [2, 2],
  [4, 3],
  [4, 5],
  [10, 3],
];
console.log(sol(28, arr));