[Algorithms] 완전탐색

문제 설명

당신에게 예산 mmm원이 있습니다.
앞에 상품이 nnn개 있고, 각 상품은 가격 + 배송비 로 구성됩니다.

단, 한 상품에 대해서는 가격을 50% 할인받을 수 있습니다.
이때, 예산 안에서 가능한 한 많은 상품을 구매하려 합니다.
과연 최대 몇 개를 살 수 있을까요?

 

---

 

늘 그랬듯 코드부터 던지겠습니다.

function solution(m, arr) {
  let answer = 0;
  const n = arr.length;

  // 총 비용(가격+배송비)으로 정렬
  arr.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));

  for (let i = 0; i < n; i++) {
    // i번째 상품을 할인받는 경우
    let money = m - (arr[i][0] / 2 + arr[i][1]);
    let cnt = 1;

    for (let j = 0; j < n; j++) {
      if (i === j) continue; // 할인받은 상품은 제외
      if (money < arr[j][0] + arr[j][1]) break; // 남은 돈보다 비싸면 중단
      money -= arr[j][0] + arr[j][1];
      cnt++;
    }

    answer = Math.max(answer, cnt);
  }

  return answer;
}

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

// 👉 출력: 4

 

---

 

문제를 읽으면 딱! 어떤 알고리즘을 써야할 지 나와야 하는데 저는 아직 부족한가 봅니다.

이건 완전탐색(블루투포스)를 써야하죠. 모든 경우의 수를 다 해보는 방법입니다.
근데 핵심은 "모든 경우의 수가 무엇인가?" 를 정확히 정의하는 겁니다.

이 문제에서는 "어떤 상품을 할인받을지"가 모든 경우의 수입니다.

 

---

1️⃣ 상품을 총 비용(가격+배송비)으로 정렬

// 할인받지 않은 상품들은 싼 것부터 사는 게 유리하므로 먼저 정렬합니다.
arr.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));

2️⃣ 한 상품을 선택해 할인 적용

// 반복문을 돌면서 한 상품씩 할인받는다고 가정하고 계산합니다.
for (let i = 0; i < n; i++) {
  let money = m - (arr[i][0] / 2 + arr[i][1]); // i번째 할인
  let cnt = 1;

3️⃣ 남은 예산으로 가능한 한 많은 상품 구매

// 싼 상품부터 차례대로 사며 예산을 소진합니다. 할인받은 상품은 건너뜁니다.
for (let j = 0; j < n; j++) {
  if (i === j) continue; // 할인받은 건 제외
  if (money < arr[j][0] + arr[j][1]) break; // 못 사면 끝
  money -= arr[j][0] + arr[j][1];
  cnt++;
}

4️⃣ 최대 개수 갱신

// 각 경우의 수마다 최댓값을 갱신합니다.
answer = Math.max(answer, cnt);

 

프로 코테 탈락러로서 볼 때, 이 정도 문제는 일반적으로 중견 2번 문제 쯤 되는 난이도이지 않을까요?