[BOJ] 백준 2293번 - 동전 1(with Java)

알고리즘

지난번에 풀었던 [BOJ] 백준 11047번 - 동전 0 문제와는 다르게 욕심쟁이 알고리즘이 아닌 '동적계획법'을 사용해야만 문제가 풀린다. 

 

우선 K번째까지의 경우의 수를 구하는 것이 목표이므로 DP 배열의 크기를 K+1로 잡아주고 dp[0]을 1로 초기화해준다. 0이 아닌 1로 초기화를 해주는 이유는 동전을 아예 사용하지 않는 경우도 경우의 수에 포함된다고 봐야하기 때문이다.

 

다음으로 이중 for문을 통해서 알고리즘이 수행된다. dp[j]는 첫번째부터 j번째까지의 동전을 사용했을 때 합이 K원이 되도록 만드는 경우의 수이다.

 

예를 들어서, 동전 각각의 가치가 2원 3원 5원이고 가치의 합이 10원이라고 해보자.

 

첫번째로 dp[j]는 2원짜리 동전으로 2원부터 10원까지 만들 수 있는 경우의 수가 각각의 dp 배열에 들어가게 된다.

 

다음으로 dp[j]는 3원짜리 동전으로 3원부터 10원까지 만들 수 있는 경우의 수가 각각의 dp 배열에 더해진다. 이때, 2원짜리 동전으로 구한 값들을 이용해서 다른 값들을 구해주게 된다.

 

마지막으로 dp[j]는 5원짜리 동전으로 5원부터 10원까지 만들 수 있는 경우의 수가 각각의 dp 배열에 더해진다. 마찬가지로 2원짜리와 3원짜리 동전으로 구한 값들을 이용해서 다른 값들을 구해주게 된다. 이렇게 마지막 동전까지 이용해서 K번째까지의 경우의 수를 구하게 되면 최종적으로 과정이 끝나게 된다.

소스코드

문제링크

2293번: 동전 1