[프로그래머스 lev1/JS] 예산

문제 출처

프로그래머스 lev1 - 예산

문제

나의 풀이 (실패)

DFS로 풀어보려 했는데 시간이 너무 오래 걸린다. 너무 어렵게 생각했나?

function solution(d, budget) {
  let ch = Array.from({length:d.length}, ()=>0);
  let tmp=[];
  let answer=0; 

  function dfs (L, sum) {
    if (sum>budget) return; 
    if (sum==budget) {
      answer = Math.max(answer, tmp.length);
    }
    else {
      for (let i=0; i<d.length; i++) {
        if (ch[i]===0) {
          ch[i]=1;
          tmp[L]=d[i];
          dfs(L+1, sum+d[i]);
          ch[i]=0; 
          tmp.pop();
        }
      }
    }
  }
  dfs(0,0);
  return answer; 
}

console.log(solution([1, 3, 2, 5, 4], 9));

다른 풀이 (통과)

문제를 잘못 이해했다.

나는 budget을 딱 맞추려고 했는데, 그럴 필요가 없었다. budget 안에서 최대한 구매하면 되는 거고, 각 부서가 신청한 금액만큼은 정확히 지원해야 한다는 거지 예산 자체를 딱 맞춰야하는 건 아니었음.

function solution(d, budget) {
  var answer = 0, sum = 0;
  d.sort((a,b) => a - b);

  for(let i = 0; i < d.length; i++){
      answer++;
      sum += d[i]

      if(sum > budget)
          answer--;
  }

  return answer;
}

console.log(solution([1, 3, 2, 5, 4], 9));