졸업 선물
선생님은 올해 졸업하는 반 학생들에게 졸업선물을 주려고 합니다.
학생들에게 인터넷 쇼핑몰에서 각자 원하는 상품을 골라 그 상품의 가격과 배송비를 제출하라
고 했습니다. 선생님이 가지고 있는 예산은 한정되어 있습니다.
현재 예산으로 최대 몇 명의 학생에게 선물을 사줄 수 있는지 구하는 프로그램을 작성하세요.
선생님은 상품 하나를 50% 할인해서(반 가격) 살 수 있는 쿠폰을 가지고 있습니다. 배송비는
할인에 포함되지 않습니다.
▣ 입력설명
첫 번째 줄에 반 학생수 N(1<=N<=1000)과 예산 M(1<=M<=100,000,000)이 주어진다.
두 번째 줄부터 N줄에 걸쳐 각 학생들이 받고 싶은 상품의 가격과 배송비가 입력됩니다.
상품가격과 배송비는 각각 100,000을 넘지 않습니다. 상품가격은 짝수로만 입력됩니다.
▣ 출력설명
첫 번째 줄에 선생님이 현재 예산으로 선물할 수 있는 최대 학생수를 출력합니다.
선생님 최소한 1개 이상의 상품을 살 수 있는 예산을 가지고 있습니다.
▣ 입력예제 1
5 28
6 6
2 2
4 3
4 5
10 3
▣ 출력예제 1
4
출력설명
(2, 2), (4, 3), (4, 5)와 (10, 3)를 할인받아 (5, 3)에 사면 비용이 4+7+9+8=28입니다.
문제를 이해해보자.
n명의 학생수가 주어지고 예산이 주어진다.
학생들은 각자 사고싶은 물건을 고를 수 있고 예산안에서 물건을 고르면 된다.
이때 배송비도 예산에 포함된다, 대신 물건들중 하나는 50% 할인을 받을 수 있다.
최대 몇명까지 물건을 사줄 수 있는지 계산하는 문제이다.
📌작성코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, product) {
let answer = 0;
let count = 1; // 상품을 구매할때마다 count + 1
let money = 0; // 돈을 저장할 변수 설정
product.sort((a, b) => ((a[0] + a[1]) - (b[0] + b[1]))) //적은 금액일수록 더 많이 살수 있으므로 오름차순 정렬
for (let i = 0; i < product.length; i++) {
money = m - ((product[i][0] / 2) + product[i][1]) //할인상품을 뺀 나머지금액
count = 1; // 이미 한개를 할인 받아서 샀기때문에 count를 1로 설정
for (let j = 0; j < product.length; j++) {
if (i !== j && product[j][0] + product[j][1] > money) { // 남은돈이 상품의 가격보다 모자르면 바로 반복문 종료
break
}
if (i !== j && product[j][0] + product[j][1] <= money) { // 남은돈이 상품을 살수 있는 정도면
money = money - (product[j][0] + product[j][1]) // 돈에서 상품값을 빼고
count = count + 1 // 카운트를(학생수) + 1
}
}
answer = Math.max(count, answer) // count와 저장되어있는 값을 비교해서 최대값만 남겨줌
}
return answer;
}
let arr = [[6, 6], [2, 2], [4, 3], [4, 5], [10, 3]];
console.log(solution(28, arr));
</script>
</body>
</html>[]우선 적은금액일수록 선물을 더 많이 살 수 있으므로 오름차순으로 정렬해준다.
=> sort 사용! sort 안에는 콜백함수가 들어가고 두개의 인자가 들어간다.
a,b를 넣어주고 ((a[0] + a[1]) - (b[0] + b[1])))를 넣어서 오름차순으로 정렬함.
첫번째 반복문을 넣어주고 돈을 저장할 변수 설정한다.
m - ((product[i][0] / 2) + product[i][1])
물건을 50%할인 받을 수 있기때문에 물건 / 2 를 하고 배송비를 더해준다.
그다음 총금액(money)에서 빼준다. 여기서 카운터를 초기화 해주어야하는데
초기화하지않으면 반복문이 끝나도 계속해서 올라가기때문에 우리가 원하는 값을 얻을 수 없다.
count = 1로 설정해준다 why? => 이미 50% 할인받아서 물건을 구매했기때문.
두번째 반복문에는 i !== j && product[j][0] + product[j][1] > money
i와 j가 같지않을때, 뒤에있는 조건을 실행해준다. (나머지금액이 상품가격보다 모자라면~)
조건이 충족하면 바로 break로 종료!
이번에는 반대로 i !== j && product[j][0] + product[j][1] <= money 남은 돈이 상품가격보다 크거나 같으면~
돈에서 상품값을 빼고 카운터를 +1 올려준다.
마지막으로 answer 에 값을 저장하고, 최종값을 비교해야하니 최대값을 구하는 메소드를 사용하여
answer와 count 를 비교해서 가장 큰 값을 answer에 넣어준다.
'알고리즘' 카테고리의 다른 글
| [알고리즘 문제] 5-1번 (0) | 2022.06.17 |
|---|---|
| [알고리즘 문제] 4-5번 (0) | 2022.06.16 |
| [알고리즘 문제] 4-3번 (1) | 2022.06.13 |
| [알고리즘 문제] 4-2번 (0) | 2022.06.13 |
| [알고리즘 문제] 4-1번 (0) | 2022.06.11 |