2022/01/20) 4. 졸업선물 [완전탐색(블루투포스)]

1. 문제

<졸업선물>
: 선생님이 학생들에게 졸업선물을 주려고 한다. 학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라고 한다. 선생님이 가지고 있는 예산은 한정되어 있다.
현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성한다. 선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있다. 배송비는 할인에 포함되지 않는다.
(첫 번째 줄에 반 학생수 N과 예산 M이 주어진다. 두 번째 줄부터 N줄에 걸쳐 각 학생들이 받고 싶은 상품의 가격과 배송비가 입력된다. 상품가격과 배송비는 각각 100,000을 넘지 않는다. 상품가격은 짝수로만 입력된다.)

2. 해결 방안

1. 지금 푸는 문제가 블루투포스!! 완전 탐색이란 걸 잊으면 안된다!!!
2. 먼저 문제를 보면, 현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하라고 한다. 그러므로 가격순대로 정렬하기 위해 sort로 정렬을 한다.
3. 한 개의 상품은 할인이 가능하므로(배송비제외), 앞에서 부터 한 번씩 할인해보자. 이게 완전탐색이지!!
4. (전체 예산 - 할인한 금액)을 money에 담고 cnt는 1로 초기화한다.
5. 말로 설명 못하겠음.. 좀 더 실력자가 되면 수정한다.
6. Math.max로 최대 개수를 answer에 담는다.
   !! 순차적으로 정렬하는 거랑, 앞에서부터 할인하는 게 핵심인듯!

! 추가 개념
-> sort

• arr.sort(); : 배열을 재정렬해준다.(배열 자체가 변경되므로 주의)
  ex1 > arr[8,3,5,1]일 때, arr.sort();하면? -> [1,3,5,8]이 된다.
  ex2 > arr["a","f","b"]일 때, arr.sort();하면? -> ["a","b","c"]가 된다.
  ex3 > arr[29,3,1,69]일 때, arr.sort();하면? -> [1,29,3,69]가 된다. 엥!?!?!?!
  => 이렇게 되는 이유는 문자열로 취급하기 때문이다. 그러므로 값을 비교해 줄 수 있는 함수를 인수로 전달해 주어야 한다.
• arr.sort((a,b)=>(a-b));
  => 설명 : 우선 sort는 배열을 순차적으로 재정렬해준다는 걸 기억하라! 그러므로 a-b를 했을 때 양수면 a가 더 크다는 것이므로, b를 a 앞으로! 만약 0이라면 그대로! 음수면 a를 b앞으로!

3. 정답

        <script>
            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));
        </script>

        <script>
            function solution(m, product){
                //최대 선물할 수 있는 개수를 담아야 하므로 숫자로 선언한다.
                let answer = 0;
                //가독성 좋게 하려고 for문 돌릴 순서 구한다.
                let n = product.length;
                //선물을 최대 많이 하는 게 핵심이다. 그러므로 작은 값들을 많이 선물해야함! 작은 값순으로 정렬한다.                
                product.sort((a,b) => (a[0]+a[1]) - (b[0]+b[1]));
                //앞에서부터 할인해보자. 완전탐색!! 어떤 값을 할인해야 최대한 많이 선물할 수 있는지!(=최대한 많은 cnt가 나올지!)
                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(i!==j && (product[j][0] + product[j][1]) > money ) break; //순차적으로 해놓은 배열이기 때문에, 예산보다 큰 선물이 나오면 더이상 선물 못함. 그러므로 굳이 돌 필요 없으므로 종료시킨다.
                        if(i!==j && (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)); //예산, 선물(값 , 배송비)
        </script>

	//어려워서 한 번 더 반복
            function solution(m, product){
                //최대로 선물할 수 있는 값을 구해야 한다. 그러므로 숫자로 선언
                let answer = 0;
                let n = product.length;
                //최대한 많이 선물을 해야 하므로, 작은 값들을 선물하는 게 유리하다! 그러므로 순서대로 정렬! sort()메소드!
                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; //할인한 거 1개 들어갔으므로
                    for(let j = 0; j < n; j ++){
                        //money보다 큰 값이 들어오면, 예산을 초과하기 때문에 바로 break해준다! 그 다음 것들은 볼 필요도 없음. 순차적으로 돼 있기 때문.
                        if(i!==j && (product[j][0]+product[j][1]) > money ) break;
                        if(i!==j && (product[j][0]+product[j][1]) <= money ){ //선물할 수 있는 조건!!
                            money -= product[j][0]+product[j][1];
                            cnt++;
                        }
                    }
                    answer = Math.max(answer, cnt);
                }
                return answer;
            }

4. 내 코드와 비교 그리고 반성

회사일 바쁘다고 안했다. 진짜로 며칠 동안 야근했음..ㅜ 하지만 하려고 하면 충분히 할 수 있었을텐데, 이런 내가 좀 아쉽다. 그래도 계속 나아가자꾸나.. 그리고 아직 난 멍청인 듯.. 어렵다