N개의 동전을 가지고 K원을 만드는 경우의 수를 구하는 방법 N = 3, K = 10이며, 1원, 2원, 5원을 무한히 가지고있을때 동전을 사용하여 10원을 만드는 경우의 수를 구하는 문제이다. 단, 중복되는 경우는 제외해야한다 예를 들어, 3원을 만들 때 1원 + 2원 == 2원 + 1원인 경우를 의미한다. 처음에는 2차원 배열을 통해 구현했다 dp[N][K] 에서 N은 각 동전까지 사용했을 때 얻을 수 있는 K원의 경우의 수를 의미한다. dp[0][0] = 1 0원을 만드는 경우의 수는 아무 동전도 사용하지 않을 때라고 생각하면 1가지이다. 또한, 1원까지 사용했을 때 만들 수 있는 K원의 개수 역시 1가지이다. 이를 표로 정리하면 아래와 같다. N | K (i | j) 0 1 2 3 4 5 6 7 ..
'Coin Change' 태그의 글 목록