d252b   4년 전

예를 들어, 1원짜리, 5원짜리, 7원짜리 동전이 있다고 하고, x원을 만드는 경우의 수는


dp[x] = dp[x-1] + dp[x-5] + dp[x-7] 

이런식으로 풀 수 있다고 알고 있습니다.

그래서 이 문제도 위의 방식을 이용하여 풀었는데요, 

만들고자 하는 금액(=money) 과  동전의 금액(=coin[index]) 라 할 때,

dp[money] +=dp[money-coin[index++]] 라고 생각을 하였습니다.

그러나 아래 코드에서 27번~33번 라인에서

주석처럼 for문의 순서가 바꾸어서 짰는데 틀렸었습니다. 

왜 coin[index]가 바깥 포문이고, money 포문이 내부 포문인가요? 

고민을 해 봐도 잘 납득이 되지 않네요.



happyleeyi   3년 전

주석처럼 하면 예를 들어 동전이 1, 3, 5가 있다 하면

1을 만들 땐 1가지 (1)

2를 만들 땐 1가지 (1,1)

3을 만들 땐 2가지 (1,1,1)(3)

4를 만들 땐 2가지 (1,1,1,1)(1,3)

5를 만들 땐 3가지 (1,1,1,1,1)(1,1,3)(5)

주석처럼 할 시에

5만들 때 = 4만들 때 + 2만들 때 + 0만들 때(1) = 2+1+1 로 4가 나와 오답입니다.

잘 보면 4에서 1을 각 더하면 (1,1,1,1,1)(1,1,3)이 나오고

2에서 3을 각 더하면(1,1,3)이 나오고

0에서 5를 더하면 (5)가 나옵니다.

따라서 (1,1,3)이 겹치는게 보이죠.

댓글을 작성하려면 로그인해야 합니다.