4-4 졸업 선물

문제

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

풀이

function solution(m, product) {
  let answer = 0;
  let n = product.length;
  product.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
  //console.log(product);
  for (let i = 0; i < n; i++) {
    let money = m - (product[i][0] / 2 + product[i][1]);
    //console.log(money);
    let cnt = 1;
    for (let j = 0; j < n; j++) {
      if (j !== i && money < product[j][0] + product[j][1]) {
        break;
      } else if (j !== i && money >= product[j][0] + product[j][1]) {
        money -= product[j][0] + product[j][1];
        console.log(money);
        cnt++;
      }
    }
    answer = Math.max(cnt, answer);
  }
  return answer;
}

let arr = [
  [6, 6],
  [2, 2],
  [4, 3],
  [4, 5],
  [10, 3],
];
console.log(solution(28, arr));

할인할 품목 하나를 정해서 머니라는 변수에 m - 할인쿠폰 쓴 상품가격 + 배송비를 미리 뺀 후

 

이중 for 문으로 완전탐색을 합니다. 할인쿠폰을 쓴 상품을 뺀 나머지 학생들의 가격+배송비를 순차정렬한 뒤

 

총 가격이 낮은 순으로 (머니 - 총 가격) > 0 이라면 카운트를 세어서 answer에 넣어줍니다.

 

틀린 풀이

function solution(m, product) {
  let answer = 0;
  let max = Number.MIN_SAFE_INTEGER;
  for (let x of product) {
    if (max < x[0]) {
      max = x[0];
    }
  }
  // console.log(max);
  for (let x of product) {
    if (x[0] === max) {
      x[0] = max / 2;
    }
  }
  //console.log(product);

  let priceArr = [];
  let sum = 0;
  for (let x of product) {
    priceArr.push(x.reduce((a, b) => a + b));
  }

  priceArr = priceArr.sort((a, b) => a - b);
  for (let i = 0; i < priceArr.length; i++) {
    if (sum + priceArr[i] > m) {
      //console.log(sum);
      break;
    }
    //console.log(priceArr[i]);
    answer++;
    sum += priceArr[i];
  }
  //console.log(priceArr);
  return answer;
}

let arr = [
  [6, 331],
  [4, 251],
  [8, 675],
  [5, 214],
  [10, 735],
  [5, 996],
  [9, 609],
  [9, 371],
  [8, 377],
  [5, 707],
  [7, 907],
  [6, 433],
  [9, 737],
  [8, 796],
  [4, 265],
  [3, 484],
  [8, 488],
  [8, 191],
  [9, 232],
  [4, 195],
];
console.log(solution(596, arr));

무작정 제일 큰 수에 할인 쿠폰을 쓴 뒤 총 가격을 순차적으로 사준다고 해도 할인쿠폰쓴 총가격 > 가진 돈 보다 큰 경우가 있기 때문에 이렇게 풀면 안되고 완전탐색 형식으로 풀어야 합니다.