[완전탐색] 졸업 선물

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

선생님은 학생들에게 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 했다.

선생님은 상품 하나를 50% 할인된 가격(배송비 포함 X)으로 살 수 있는 쿠폰을 가지고 있으며 선생님이 가지고 있는 예산은 한정되어 있다.

현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 가능한 최대 학생수를 출력한다.

 

 

👉 입력

첫 번째 줄에 학생수(N)과 예산(M)이 주어진다.

두 번째 줄부터 N줄에 걸쳐 학생들이 받고 싶은 상품의 가격과 배송비가 입력된다.

단, 상품 가격은 짝수로만 입력되며 최소한 1개 이상의 상품을 살 수 있는 예산이 주어진다.

 

 

👈 출력

현재 예산으로 선물할 수 있는 최대 학생 수를 출력한다.

 

 

📝 풀이

 

function solution(m, product) {
    let answer = 0;
    product.sort((a, b) => (a[0] + a[1]) - (b[0] + b[1]));

    for (let i = 0; i < product.length; i++) {
        let money = m - (product[i][0] / 2 + product[i][1]); // 남은 예산
        let count = 1;

        for (let j = 0; j < product.length; j++) {
            if (j !== i && (product[j][0] + product[j][1]) > money) break;

            if (j !== i && (product[j][0] + product[j][1]) <= money) {
                count++;
                money -= (product[j][0] + product[j][1]);
            }
        }
        answer = answer > count ? answer : count;
    }
    return answer;
}

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

 

먼저 주어진 배열 product를 상품의 가격과 배송비를 합한 것이 작은 순서대로 정렬한다.

정렬을 거치고 나면 product는 [ [2, 2], [4, 3], [4, 5], [6, 6], [10, 3] ]이 된다.

 

첫 번째 for문에서는 할인받을 상품을 결정한다.

모든 상품을 하나씩 할인해보면서 가능한 경우의 수를 하나씩 다 경험해보는 것이다.

 

주어진 예산 m에서 할인받을 상품의 할인된 가격과 배송비를 더한 해당 상품의 가격을 뺀다.

그리고 해당 상품은 구매한 것이기 때문에 count는 1부터 시작한다.

 

이후 할인받은 상품을 뺀 나머지 상품을 작은 것부터 담는다.

이때 예산이 초과했다면 순회를 멈춘다.

 

예산 안에서 물건을 모두 담았다면 그 경우의 수를 answer에 담으며 최댓값을 갱신한다.

모든 순회가 끝나면 answer에는 가능한 경우의 수 중 최댓값이 남게 되므로 answer를 리턴, 출력한다.