[완전 탐색] 졸업 선물

현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하시오

선생님이 가지고 있는 예산은 한정

선생님은 상품 하나를 50% 할인해서 살 수 있는 쿠폰 보유
(단, 배송비는 할인에 포함 X)

입력 예제

첫 번째 줄은 반 학생수 N(1<=N<=1000)과 예산 M(1<=M<=100,000,000)

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

상품가격과 배송비는 각각 100,000을 넘지 X

상품가격은 짝수로만 입력됩니다.

현재 예산 : 28

function solution(m,arr) {
    let answer = 0;

    // 1. 상품 + 배송비 합 정렬
    arr.sort((a,b)=>(a[0]+a[1])-(b[0]+b[1]));
  
   // 2. 값이 작은 것부터 차례로 50% 할인 적용
    for(let i=0; i<arr.length; i++){
        let money = m - (arr[i][0]/2 + arr[i][1]);
        let num = 1;
      	
      	// 3. 예산에서 50% 할인 적용한 것을 뺀 나머지 예산으로 선물을 살 수 있는 최대 갯수 구하기
        for(let j=0; j<arr.length; j++) {
            
            // 남은 예산이 선물 값보다 작다면 for문 종료
            if(j!==i && (arr[j][0]+arr[j][1]) > money) break;
          
            // 남은 예산이 선물 값보다 같거나 크면 선물 값을 돌면서 예산에서 빼주며 학생 수를 구함
            if(j!==i && (arr[j][0]+arr[j][1]) <= money) {
                money -= (arr[j][0]+arr[j][1]);
                num++;
            }
        }
        
      	// 4. num은 최대로 사 줄 수 있는 학생 수, 가장 큰 num을 answer로 반환
        answer = Math.max(answer, num);
    }

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

• 가장 먼저 ( 상품 + 배송비 ) 값이 가장 작은 순으로 배열을 정렬

• 값이 가장 작은 것부터 차례로 50% 할인을 적용

• 예산에서 할인된 값을 제외하고, 남은 예산으로 몇 명의 학생들에게 사 줄 수 있는지 구함

(10, 3)를 할인받아 (5, 3)에 사면 최대 4명의 학생에게 선물을 줄 수 있다.

배열을 순차적으로 모두 탐색하여 비교하는 것이 포인트!!