JS알고리즘 | 완전탐색 - 졸업선물

문제

원하는 상품을 골라 가격과 배송비를 제출하라

현재 예산으로 최대 몇 명의 학생에서 선물을 사줄 수 있는지

상품 하나를 50% 할인해서 살 수 있는 쿠폰 있다. 배송비는 할인에 포함되지 않는다.

 

입력예제 |

예산 28

제출한 가격과 배송비 [6, 6], [2, 2], [4, 3], [4, 5], [10, 3]

출력예제 |

4

 

풀이

총 비용을 기준으로 정렬을 한다.

쿠폰을 어떤 가격에 적용시켜야하는가 -> 기준이 없기 때문에 모든 경우를 다 찾아봐야한다. 

 

첫 번째 상품을 할인받는다 생각하고, 총 비용에서 제외하고 계산

두 번째 상품을 할인받는다 생각하고 총 비용에서 제외하고 계산

.

.

.

다 해보는 것이 완전탐색

 

a[0]+a[1]  상품가격+배송비

 

전체 비용해서 첫 번째 금액을 할인해서 뺀다. → 카운팅은 1부터 시작

 

 

코드

const solution = (budget, product) => {
  let answer = 0;
  let n = product.length;

  product.sort((a, b) => (a[0] + a[1]) - (b[0] + b[1])); // 총합 순서대로 오름차순 정렬 먼저해주기

  // for문 돌면서 모든 상품이 한 번씩 할인받는 경우 해보기
  for (let i = 0; i < n; i++) {
    // 전체 예산 구하기
    let money = budget - (product[i][0] / 2 + product[i][1]); // 할인받은 금액을 전체 예산에서 뺀다.(산 경우로 계산)
    let count = 1; // 위의 계산으로 1개는 계산했다는 가정으로 1부터 시작함
    for (let j = 0; j < n; j++) {
      // i는 이미 할인된 상품이므로 j가 i랑 같은 경우는 안되도록 처리
      if (j !== i && (product[j][0] + product[j][1]) > money) break; // 사려고하는 것이 남은 예산보다 큰 경우 break;
      if (j !== i && (product[j][0] + product[j][1]) <= money) { // 남은예산보다 작거나 같아야한다.
        money -= (product[j][0] + product[j][1]); // 전체에서 비용 빼주기
        count++; // 상품 개수 카운팅
      }
    }
    answer = Math.max(answer, count);
  }
  return answer;
}

const budget = 28;
const product = [[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]];
console.log(solution(budget, product));

주석 없는 전체코드

const solution = (budget, product) => {
  let answer = 0;
  let n = product.length;

  product.sort((a, b) => (a[0] + a[1]) - (b[0] + b[1]));

  for (let i = 0; i < n; i++) {
    let money = budget - (product[i][0] / 2 + product[i][1]); 
    let count = 1;
    for (let j = 0; j < n; j++) {
      if (j !== i && (product[j][0] + product[j][1]) > money) break;
      if (j !== i && (product[j][0] + product[j][1]) <= money) {
        money -= (product[j][0] + product[j][1]);
        count++;
      }
    }
    answer = Math.max(answer, count);
  }
  return answer;
}

const budget = 28;
const product = [[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]];
console.log(solution(budget, product));