[알고리즘/인프런] 졸업 선물

문제

---

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

 

풀이

---

// 각 학생을 포함시킬 때 pp에 상품가를 저장하고 pd에 배송비를 더한다.
// pp에서 최댓값에 50%를 계산해 모두 더한다.
// 더한 값이 최댓값이라면 answer에 cnt를 할당한다.

function solution(M, arr) {
  const N = arr.length;
  let answer = Number.MIN_SAFE_INTEGER;
  arr.sort((a, b) => a[0] + a[1] - b[0] + b[1]);

  for (let i = 0; i < N; i++) {
    let pp = []; // 상품 가격
    let pd = 0; // 배송비
    let cnt = 1;
    pp.push(arr[i][0]);
    pd += arr[i][1];
    
    for (let j = i + 1; j < N; j++) {
      pp.push(arr[j][0]);
      pd += arr[j][1];
      cnt++;

      const maxPrice = Math.max(...pp);
      // 총 가격 계산
      const totalProductPrice = pp.reduce((total, val) => {
        if (val === maxPrice) total += val / 2;
        else total += val;
        return total;
      }, 0);
      const totalPrice = totalProductPrice + pd;
      // 예산 넘을 경우 중단 
      if (totalPrice > M) break;
      answer = Math.max(answer, cnt);
    }
  }

  return answer;
}