PROGRAMMERS_002

문제

문제

해결

function solution(n, money) {    
    let answer =  Array.from({length: n+1}, () => 0);
    answer[0] = 1;
    
    for (coin of money){
        for (let i = 1; i <= n; i++){
            if (i - coin >= 0 && answer[i - coin]) 
                answer[i] = (answer[i] + answer[i - coin]) % 1000000007;
        }
    }
    
    return answer[n];
}

풀이

• 동적 프로그래밍 사용 (DP) ![[Pasted image 20231011112619.png]]

• ==DP?== 큰 문제를 작은 문제로 나누어 푸는 문제 참고

• 위 문제에서 코인 먼저 루프를 돌려야 중복이 생기지 않아 정확한 답이 나옴

• if 문으로 거르지 않고 js 문법인 ?? 를 이용하면 효율성에서 시간초과

  // 효율성 통과
  if (i - coin >= 0 && answer[i - coin]) 
  	answer[i] = (answer[i] + answer[i - coin]) % 1000000007;
  
  // 효율성 시간초과
  answer[i] = (answer[i] + (answer[i - coin] ?? 0)) % 1000000007;