백준 9084

흐흑

너무 어려웠다

경우의 수를 구하는 문제였는데, 뭔가 묘하게 이해가 될까 말까 했다.

 

현재 금액을 만들 수 있는 가짓 수를 찾는 문제인데

 

이해하기 쉽게 가정을 해본다. 

 

[동전]

번호  1     2      3      4 

금액  10   20   30   40 

 

60원을 만들기 위해서는 동전의 개수만큼 루프를 돈다

     해당 인덱스의 동전이 만들 수 있는 금액부터 최대액 까지 루프를 돈다.

           이 금액을 만들기 위한 가지수는  루프를 돌면서 [금액- 현재 동전의 가치] 만큼씩 더해준다

---

for(동전의 가지수 i)

     for(가능한 금액 j)

           dp[금액 j] += dp[금약 j - i 번째 동전의 개수]

---

 

이런 식의 루프를 형성한다.

 제일 중요하다고 생각한 부분은 dp배열은 0으로 초기화 하면서

dp[0]의 값은 1

로 주는 것이다.

이렇게 배열을 설정해주면 동전으로 나눠 떨어지는 가능한 경우의 수만을 셀 수 있게 된다.