🔎 숫자의 표현

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/12907

📄 제출 코드

function solution(n, money) {
  let arr = new Array(n).fill(0);
  arr.unshift(1);
  console.log(arr);
  money.forEach(el => {
    for (let i = el; i < n + 1; i++) {
      arr[i] += arr[i - el];
    }
  });
  
  return arr[n] % 1000000007;
}

let n = 5;
let money = [1, 2, 5];
console.log(solution(n, money));

money에 있는 돈들로 n을 만들 수 있는 방법 수를 구하는 문제다.
처음에 수열을 생각하고 풀었는데 효율성에서 다 실패가 떳다.
다른 방법을 생각해보다가 결국 다른 사람의 코드를 보게되었다.
처음에 이해가 잘 안됐는데 블로그에 설명이 잘 되있어 이해하는데 도움이 많이 되었다.

5의 경우
money : 1, 2, 5

먼저 임의 배열을 만든다.
배열의 크기는 0~N까지다.
첫 idx는 0을 만드는 방법. 즉 아무것도 내지 않을때 1가지 이다.
뒤의 idx들은 각각 money의 숫자를 최소 1개 사용해서 덧셈을 이용하여 인덱스 값을 구할 수 있는 경우의 수이다.
2의경우 2~5까지 생각함.

testCase 01
1번 테스트 케이스 경우.
MONEY 1 일 때,
0 1 2 3 4 5
1 1 1 1 1 1
1은 1~5까지 모두 1번이상 사용해서 만들 수 있다.

MONEY 2 일 때,
0 1 2 3 4 5
1 1 2 2 3 3
2는 2~5까지 모두 1번이상 사용해서 만들 수 있다.
4의 경우 1 1 2 / 2 2 , 2번 사용된다.
5의 경우도 위와 같이 2번 사용된다.

MONEY 5
0 1 2 3 4 5
1 1 2 2 3 4
마지막으로 5한번 쓰는경우로 dp[5]에 한번 더 추가된다.

식으로 나타내기위해 money의 경우를 모두 돌아야하니 forEach를 이용.
el부터 n까지 돌면서 for(let i=el; i < n+1; i++)
i를 만들때 el이 사용되는 횟수.
arr[i] += arr[i-el]