[완전탐색]졸업 선물

문제

선생님은 올해 졸업하는 반 학생들에게 졸업 선물을 주려고 한다.학생들에게 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 하였다. 선생님이 가지고 있는 예산은 한정되어 있다.현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하고자 한다.선생님은 상품 하나를 50% 할인해서 살 수 있는 쿠폰을 가지고 있다. 배송비는 할인에 포함되지 않는다.(선생님은 최소한 1개 이상의 상품을 살 수 있는 예산을 가지고 있다)

 

문제풀이

예산에 맞게 학생들에게 선물을 줄 수 있는 경우의 수는 총 4가지이다.2명의 학생에게 살 수 있는 예산, 3명의 학생에게 살 수 있는 예산, 4명의 학생에게 살 수 있는 예산, 5명의 학생에게 살 수 있는 예산으로 나눌 수 있다. 이때 선생님은 최소한 1개 이상의 선물을 살 수 있는 예산이 있기 때문에 1명의 학생에게 살 수 있는 예산과 같은 경우는 탐색에서 제외할 수 있다.

 

5명의 학생 중에서 r명을 뽑는 조합을 이용해야 하는 문제이다. 이때 r = 2, 3, 4, 5(명) 순으로 증가하고 r이 증가할 때마다 4번의 반복문을 수행하되 다음 인덱스 요소를 참조하기 위해 각 반복문의 인덱스 초기값은 이전 인덱스의 초기값에 1을 가산해줘야 한다.

 

예산 한도를 넘기지 않고 예산을 전부 소비했을 때의 학생 수가 최대 값이 되기 때문에 각 경우의 조합들의 합산 값을 예산과 비교해주었다. 선생님은 한 상품에 대해서만 50%을 할인할 수 있는 쿠폰이 있기 때문에 조합 중 마지막 조합의 상품에 관해서만 0.5를 곱해주고 배송비에 해당하는 인덱스 요소를 별도로 합산해주어 해당 조건을 만족시켰다.

 

코드

function solution(stu, budget, arr) {
  let answer = [];
  let sumArr = [];

  for(let i = 0; i < arr.length; i++) {
    let sum = 0;
    for(let j = 0; j < arr[i].length; j++) {
      sum += arr[i][j];
    }
    sumArr.push(sum);
  }

  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
        if(sumArr[i] + ((arr[j][0] * 0.5) + (arr[j][1])) === 28) {
          answer.push([arr[i], arr[j]]);
        }
      for(let z = j + 1; z < arr.length; z++) {
        if(sumArr[i] + sumArr[j] + ((arr[z][0] * 0.5) + (arr[z][1])) ===28) {
          answer.push([arr[i], arr[j], arr[z]]);
        }
        for(let h = z + 1; h < arr.length; h++) {
          if(sumArr[i] + sumArr[j] + sumArr[z] + ((arr[h][0] * 0.5) + (arr[h][1])) === 28) {
            answer.push([[arr[i], arr[j], arr[z], arr[h]]]);
          }
          for(let s = h + 1; s < arr.length; s++) {
            if(sumArr[i] + sumArr[j] + sumArr[z] + sumArr[h] + ((arr[s][0] * 0.5) + (arr[s][1])) === 28) {
              answer.push([arr[i], arr[j], arr[z], arr[h], arr[h], arr[s]]);
            }
          }
        }
      }
    } 
  }

  return answer[0][0].length;
}
let stu = 5;
let budget = 28;
let arr = [[6,6], [2,2], [4,3], [4,5], [10, 3]]
console.log(solution(stu, budget, arr));

 

오답

50%의 할인 쿠폰을 어느 상품에 적용하냐에 따라 선물을 받을 수 있는 학생의 수가 달라지기 때문에 어떤 상품에 할인을 적용할지를 경우의 수 기준으로 잡는다면 조회 및 참조의 반복을 줄일 수 있다.(사실상 2명의 학생에게 선물을 나눠줄 수 있는 경우와 5명의 학생에게 선물을 나눠줄 수 있는 경우는 검사해보지 않아도 예산 내에서 만족할 만한 답을 찾아내기가 어렵기 때문에 불필요한 연산 과정이라고 생각한다)

 

또한 위의 풀이에서는 예산을 전부 사용하였을 때가 선물을 나눠 줄 수 있는 학생의 수가 가장 많다고 가정하였지만(실제 정답 또한 예산 28을 모두 소비했을 때 선물을 사 줄 수 있는 최대 학생 수를 찾을 수 있었다) 예산보다 낮은 금액에서 최대 학생 수가 나올 수도 있기 때문에 합산이 예산과 같다는 조건식을 통해 답을 찾는 것은 적합하지 않다.

 

이때 선물을 줄 수 있는 최대 학생 수를 구해야 하기 때문에 가장 작은 값에 할인율을 적용시키고 이후 최대한으로 남긴 금액을 가지고 남은 상품들을 구매할 수 있도록 해야 하기 때문에 상품 리스트를 Array.sort()로 오름차순 정렬시켜 주었다.

 

코드

function solution(m, 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 = m - (product[i][0] / 2 + product[i][1]);
    let cnt = 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];
        cnt++;
      }
    }
    answer = Math.max(answer, cnt);
  }

  return answer;
}

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