전혀 접근을 못하겠었는데,
'시간 복잡도 생각 1도 안하고 풀어보자' 하니까 풀렸다.일단 어차피 나는 짬이 안되니 시간복잡도를 고려하지 말고
Brute Force로 일단 들이받는 연습을 많이 해야겠다.
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));
function solution(m, product) {
let max = Number.MIN_SAFE_INTEGER;
for (let i in product) {
let arr = product;
// i 번째 선물에 쿠폰 적용
arr[i][0] /= 2;
arr = arr.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
let cnt = 0;
let sum = 0;
for (let x of arr) {
if (sum >= m) {
if (max < cnt) max = cnt;
break;
}
sum += x[0] + x[1];
cnt++;
}
}
answer = max;
return answer;
}
let arr = [
[6, 6],
[2, 2],
[4, 3],
[4, 5],
[10, 3]
];
console.log(solution(28, arr));
- product 배열을 먼저 sort 했어도 됐을듯 하다.
- 일단 할인쿠폰을 적용한 선물부터 예산에서 빼고 나머지를 카운트하는 것이
맞는 것 같다.
(할인쿠폰만 적용하고 실제로 사지는 못하는 경우가 카운트됐을 것 같다)
- 그래도 내 힘으로 Brute Force로 들이받는 시도를 성공한 것 같아서 뿌듯하다
sort()
를 잘 사용한 것 같아서 기쁘다