이 문제는 겉으로는 쉬워 보이려고 하는 아주 어려운 친구죠.
저도 이 친구한테 완전 속아 넘어갔습니다.
난이도가 장난 아니게 어려운 문제입니다.
카테고리가 연습문제라고 하는데, 제가 보기엔 댕댕이 소리 같습니다.

먼저 이 문제는 dp유형의 문제입니다.
시간 효율성이 빡세면 거의 dp, 해시, 투포인터 등등일 확률이 높습니다.
이 문제는 그 중에서도 다이나믹 프로그래밍인 dp의 사용을 요구하는 문제입니다.

일단 완전탐색으로 답을 구해, 중복제거를 하여, 시간초과를 맞이한 저와 같은 친구들 환영합니다.

이 문제의 dp배열 먼저 정의 해보겠습니다.
n = 5, money = [1, 2, 5]인 테스트 케이스 기준입니다. 배열의 크기는 n+1입니다.

인덱스	0	1	2	3	4	5
dp	1	0	0	0	0	0

위의 표의 인덱스는 각각의 가격을 의미합니다.
다만 0일 경우에는 무조건 나누어 떨어진다는 의미로 항상 1의 값을 가집니다.
이 부분은 계속 읽어보시면 이해하실 수 있도록 노력 좀 해보겠습니다.

전체적인 알고리즘을 말하자면, money배열에 있는 값을 하나씩 가져오면서 반복문을 돌리기 시작합니다.
1번 인덱스는 1원을 지불하기 위한 방법의 수를 가리킵니다. 마찬가지로 2, 3, 4도 입니다.
5번 인덱스도, 5원을 지불하기 위한 방법의 경우의 수를 의미합니다. 이 부분이 최종 답이 됩니다.
저희는 5번 인덱스에 답이 입력될 수 있도록 값을 유도하려고 할 겁니다.
여기서 의문이 생기실 분은 무조건 있으실 겁니다. 5원의 경우의 수만 알면 될 텐데, 왜 굳이 0원부터 n 까지의 경우의 수를 모두 구하느냐 라고 말이죠.

흠, 그럼 왜 n원에 해당되는 값 이외에, 그 아래의 가격이 만들어질 수 있는 경우의 수를 왜 구하는지 부터 알아야겠죠?

예를 들어봅시다.
1원과 2원을 가지고 4원을 만들어보겠습니다.
1원으로 그럼 1~4원을 확인해서 1으로 만들어 볼 수 있는 방법은 전부 다입니다.
1원일 경우 1원 1개만 지불하면 되죠, 2원은 1원 2개를 지불하면 되죠, 마찬가지로 4까지 해당됩니다.
그럼 각 dp배열에 1씩 추가 해줍니다. 그 의미는 해당 액수에는 현재 화폐로는 1가지의 방법으로 만들 수 있는 의미죠.
1원은 한 종류밖에 없으니, 경우의 수는 하나 입니다. 1원 3개 낸다고 경우의 수가 3개로 늘어난다고 생각하시면 큰일납니다 ;;;
단순히 생각해도 1원으로 3원을 내려면 1원 3개 내는 거 말고는 방법이 없습니다. 만약 있으면 화폐 훼손죄가 성립이 됩니다. ㄷㄷ(그냥 농담입니다 ㅎ)
그럼 이제 1원으로는 각각 액수마다 한 개의 경우의 수가 존재한다는 걸 우리는 알았습니다.
그럼 2원을 추가해봅시다. 그 의미는 기존의 경우의 수에 2원을 껴서 생각해보자는 것입니다. 뭐 그래도 달라지는 건 별로 없습니다.
2원으로 1원은 만들 수 없으니 패스합니다. 2~4원을 보도록 합니다.
2원을 보자면, 2원 하나로 지불이 가능하죠? 즉, 그러면 경우의 수가 추가된다고 볼 수 있습니다.
하지만, 잘 보시면, 기존의 2원에는 1원 짜리 2개로도 지불이 가능하므로 경우의 수 1개가 이미 존재합니다.
그렇지만 새로이 추가 된 2원으로도 값을 정확히 지불이 가능하죠? 그럼 1을 더해주어 2를 올려줍니다.
이 때, 사용하는 점화식이 바로,

dp[현재해당가격] += dp[현재해당가격 - 현재화폐의액수] 라는 점화식이 생깁니다. (중간에 '+=' 입니다. 중요합니다!!! '=' 아닙니당)

같이 한 번 파헤쳐 봅시다.
현재 값은 2원이니까, dp의 두 번째 인덱스가 해당됩니다. 그럼 기존의 1원을 지불했던 경우의 수가 존재하므로, 1이 이미 계산되어있겠죠?
그 다음 식은, 현재해당가격에서 현재화폐의액수를 빼는 겁니다. 이렇게 되면 현재 2원을 계산하고 있고, 2원을 빼는 거죠.
이 의미는 무엇이냐면, 현재 가격에서 현재 화폐를 하나 지불하게 되면, 남은 돈이 생깁니다. 그러면 남은 돈의 인덱스를 참조하여, 그 남은 돈을
만들 수 있는 경우의 수를 가져오는 겁니다. 현재를 보자면 2원을 계산하고 2원짜리를 내면 우측항의 값은 0이 되버립니다. 그 값을 dp의 인덱스로 참조합니다.
0은 항상 1로 고정하는 이유가 바로 여기서 나옵니다. 2원에서 정확히 2원을 내게 되면, 당연히 낼 수 있고, 추가적으로 내야 할 돈이 생기지 않습니다.
그래서 항상 0번 인덱스는 추가적으로 내지 않는 화폐 단위를 위해 항상 값이 1이 되어야합니다.
그럼 dp[2] += dp[2-2] 가 되어 2원의 경우의 수에 1이 새로이 추가되겠죠? 그럼 dp[2]의 값은 1에서 2로 바뀝니다. (1 + 1 = 2)
마찬가지로 2원으로 3원을 지불해봅시다.
점화식에 의해서

dp[3] += dp[3 - 2] 가 됩니다. dp[1]의 값은 아까 1원의 경우에서 이미 한 번의 경우의 수가 나왔기 때문에 1이 기록되어있습니다.
그럼 dp[3]도 마찬가지로 1원의 경우의 수인 1이 기록되어있죠. 두 값을 더해주어 dp[3]에 갱신이 됩니다. 1이 2로 증가합니다.
여기서 3원을 계산합니다. 2원을 내게 되면, 1원이 남게되죠? 그 1원을 1원을 만들 수 있는 경우의 수를 더해주어서 계산합니다.
왜 이런 짓을 하냐면, 2원을 이미 내고 나면, 나머지 1원은 어떤 방식으로 만들든 간에 경우의 수는 같습니다.
즉 여기서는, 2원을 내서 3원을 내는 경우의 수는 2원을 내고 나머지 1원을 만드는 경우의 수와 같다고 보는 겁니다.(이해가 되시나요?)

자 이제 본론으로 돌아가서 테스트 케이스를 가지고 위의 점화식을 증명해봅시다.

TestCase1) n = 5, money[1, 2, 5]

1원 짜리 화폐 계산.

인덱스	0	1	2	3	4	5
dp	1	0+1=1	0+1=1	0+1=1	0+1=1	0+1=1

1원 화폐를 계산하게 되면, 위와 같이 순서대로 값이 갱신 되어 전부 1이 될 겁니다.
1원일 경우 1원 1개만 내면 됩니다. 남은 돈은 0원이므로 0번 인덱스의 1을 더해줍니다.
2원일 경우 1원을 1개 내면 1원이 남습니다. 1원을 내는 경우의 수는 방금 계산한 값입니다. 1이 됩니다. 1을 더해주어 값이 1이 됩니다.
3원일 경우 1원을 1개 내면 2원이 남습니다. 2원을 내는 경우의 수는 방금 계산했습니다. 1을 더해주어 값이 1이 됩니다.
5원까지 전부 계산하면, 모든 값이 1이 됩니다.

2원 짜리 화폐 계산.

인덱스	0	1	2	3	4	5
dp	1	1	1+1=2	1+1=2	1+2=3	1+2=3

1원은 계산할 수 없습니다. 점화식이 사용될 수 있는 조건은 현재 금액이 화폐단위 이상이어야 가능합니다. 그 이외에는 계산하면 에러나고, 계산 할 필요조차 없습니다.
2원은 2원 짜리 1개로 가능합니다. 정확한 값을 지불하여 0번인덱스 참조 되어 1(기존값) + 1(0번인덱스참조값) = 2가 갱신됩니다.
3원은 2원 짜리 1개 내고, 나머지 1원 입니다. 1원을 만들 수 있는 경우의 수를 더합니다. 1(기존값) + 1(1원을 만드는 경우의 수) = 2가 갱신됩니다.
4원은 2원 짜리 1개 내고, 나머지 2원 입니다. 2원을 만들 수 있는 경우의 수는 새로 갱신 된 값을 그대로 참조합니다. 1(기존값) + 2(2원을 만드는 경우) = 3이 갱신됩니다.
5원은 2원 짜리 1개 내고, 나머지 3원 입니다. 3원을 만들 수 있는 경우의 수도 새로 갱신 한 거 사용하도록 합니다. 1(기존값) + 2(3원을 만드는 경우) = 3이 갱신됩니다.

여기서 이 점화식의 진가가 발휘됩니다. 사실 보시면 이해가 안되실만한 부분이라함은, 2원으로 4를 계산할 때,
2가 두 번 들어가는 부분은 고려 안하나요? 라는 물음이 발생 할 수 있습니다. 저도 또한 같은 생각을 하였습니다.
사실 2를 한 번 내면 나머지 2원을 만드는 경우의 수를 참조합니다. 하지만 이 값에 이미 2를 만드는 경우를 1원 2개 짜리와, 2원 1개를 합해 총 2가지의 경우가 있다고,
값을 저장하였기 때문에, 고려를 굳이 안해도 자연스럽게 2원 짜리를 2개 쓴 경우까지 계산이 됩니다. 마찬가지로 다른 예를 들자면,
2원 짜리로 8원을 만든다고 하면, 8원에서 2원을 내고 남은 6원의 경우의 수가 있겠죠?
그 6원에서도 2원 짜리로 지불한다고 하는 경우가 있고, 남은 4원에서도, 남은 2원에서도 쭉 이어집니다. 잘만 생각하면, 쓸데없는 고민이 될 뿐이죠..

5원 짜리 화폐 계산.

인덱스	0	1	2	3	4	5
dp	1	1	2	2	3	3+1 = 4

마지막으로 5원 짜리의 화폐를 계산합니다.
현재 금액은 반드시 단위 화폐 이상일 경우만 계산이 가능하다고 했으므로,
5원을 지불하는 경우만 계산이 됩니다. 당연히 정확히 지불이 되므로, 0번 인덱스를 참조합니다.
1값을 가져오고, 기존 값인 3을 더해 총 4가지의 경우의 수 있다는 것을 알 수 있습니다.

인터넷에 나오는 해설들을 참고하여 저도 이 문제를 풀었습니다.
하지만, 큰 틀은 알려주지만, 왜 이 값이 이런 식으로 세세하게 알려준 부분이 많이 미흡하여,
저는 그렇게 머리가 좋지 않아 20번은 정독 한 후에 비로소 깨달았습니다.

제가 이 문제를 접하면서, 생각했던 의문점은, 초심자들 모두 마찬가지라 생각하여 이 해설을 작성하였습니다.
부디 좌절하는 일이 없길 바랍니다.
오타가 생길 수도 있으니 지적 부탁드립니다.