[백준 알고리즘] 2294번 동전 2

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)

입력과 출력

첫째줄에 n, k가 주어지고 n개의 동전가치가 차례대로 들어오며 k는 만들어야하는 가치의 금액이다 출력은 사용한 동전의 최소 개수이다

풀이

전에 2원 6원 8원으로 k원을 만드는 비슷한 문제들을 풀어본적이 있는데 이건 아예 항상 사용할 수 있는 동전의 개수도 다르고 종류도 다르다

길이가 k인 배열을 만들고 각 금액을 만드는 최소 개수를 저장해 나가면서 k자리의 값을 을 구한다

불가능한 경우에는 -1을 출력하므로 배열은 -1로 초기화한다

n개의 동전이 들어오면 가장 작은 금액의 동전부터 반복문을 시작한다 

임의로 들어온 n개의 동전을 입력순서대로 a, b, c, d, ... 로 생각해서 점화식을 세워본다

간단하게 적으면 다음과 같고

f(k) = min(dp[k/a], dp[k/b], dp[k/c], ... ,) + 1

자세히 조건까지 적어보면

if ( k이 a로 나눠지면 )

dp[k] = dp[k/a] +1 ;

if ( k이 b로 나눠지면 )

dp[k] = dp[k/b] +1 ;

if ( k이 c로 나눠지면 )

dp[k] = dp[k/c] +1 ;

if ( k이 d로 나눠지면 )

dp[k] = dp[k/d] +1 ;

와 같이 각각의 동전으로 나눠지는지 확인하고 가능한 경우의 값들중에 최소값에 +1을 해주면 k의 가치를 만들 수 있는 최소한 동전개수를 만들 수 있다

...라고 바보같이 너무 단순하게 문제를 생각했다(어제......)

1차원 dp 배열만 있으면 될거라생각했는데 동전의 종류가 n개 이기때문에 각 k원에 대해서 동전 n가지의 모든 경우를 구해야하는거같다

k원에 대해서 n가지의 최소 동전개수를 나타내도록 점화식을 세우면 

f(n, k) = n번째 동전부터 사용해서 k원을 나타내는 최소 동전 개수 

맨처음 f(0, k)를 호출해서 풀어나간다

f(i, k) ->i는 입력받은 동전의 금액중 i번째 동전을 의미

1. 0 -> i=n 이고 k=0

2. 불가능한 경우 -> i=n이고 k > 0 마지막동전인데 아직 k원만큼 남아있을때

3. f(i+1, k) ->k<coin[i], n번째 동전을 사용할 수 없을 때(남은가치가 동전보다 작지않는한 무조건 사용가능하니까)

4. min( f(i+1, k), f(n, k-coin[i])+1) ->k>= coin[i] 일때 해당동전을 사용하거나, 안한것 중 작은값을 택함

f(i+1, k) 이부분은 i번째 동전이 사용되지 않을 경우인데, 계속 나는 금액이 해당 동전으로 나눠져야 사용할 수 있다고 생각을 했다... 그래서 위에 조건식이 모두 금액을 동전으로 나누게 만들었는데 그래서 이상했다 나눠지는 동전으로만 만든다고 최소의 동전개수가 아니라는걸 생각을 안하고 풀었다.....

* 백준 채점이 너무 느려진거같다......하나 채점하는데 10분은 기다려야한다 왜지 ㅠㅠ

코드

int coins(int i, int k)

{

int result;

if(i==n && k==0)

return 0;

if(i==n && k>0)

return impossible;

if(dp[i][k] != -1 ) return dp[i][k];

result = coins(i+1, k);

if(k>=coin[i])

result = min(result, coins(i, k-coin[i])+1);

dp[i][k] = result;

return result;

}