두 코드 모두 결과는 동일하게 출력 되지만, IDE에서 여러 예제 입력들을 돌려보면 결과 출력 속도가 확연하게 차이 나는 것을 확인할 수 있었습니다.

예상하기로는 재귀 호출된 DFS 함수들이 스택에 너무 많이 쌓이면서 이러한 시간 차이가 발생하지 않나 싶지만, 혹여나 고수 분들의 생각은 다를 수도 있을 것 같아서 이렇게 질문 드립니다!

코드에 대한 간략한 설명은 아래에 정리하였습니다.

---------------------------------------------------------------------------------------------------------------------------------------------------

첫 번째 코드는 DFS을 이용한 풀이입니다.

인덱스를 오름차순으로 탐색하며 다음의 두 가지 경우로 탐색합니다.

- sum에 현재 인덱스의 동전을 더함, 인덱스 변화 x

- sum에 현재 인덱스의 동전을 더하지 않고, 다음 인덱스로 이동

탐색 종료 조건 : 인덱스 범위를 벗어나거나, 동전의 합이 k이상인 경우이며, 동전의 합이 k이면 cnt에 경우의 수 1을 증가

두 번째 코드는 DP를 이용한 풀이입니다.

- dp[i] = j : i원을 만들 수 있는 경우가 j가지

- dp[j] += dp[j - coin[i]] : i원짜리 동전을 이용하여 j원을 만드는 경우의 수를 dp[j]에 더함

이를 이용하여 아래와 같이 반복문을 통해 모든 경우의 수를 구합니다.

for (int i = 1; i <= n; i++) 

    for (int j = coin[i]; j <= k; j++) 

         dp[j] += dp[j - coin[i]];