2293 동전 1

https://www.acmicpc.net/problem/2293

2293번: 동전 1

배낭문제의 아류처럼 보이는데, 예전에 했었던 코드들을 살펴봐도 도저히 몰랐다.

 

지금까지 풀어본 문제중에 비슷했던 것은 N개의 동전들로 K원을 만들 때 최소개수를 구하는 문제였다.

 

하지만 이 문제는 경우의 수를 구하는 문제여서 매우 헷갈렸다.

 

10번이나 틀리며 한참 고민한 끝에 상당히 간단한 문제임을 깨달았다.

 

설명이 난잡하기 때문에 더 좋은 블로그를 소개해야겠다.

 

https://gurumee92.tistory.com/64

[프로그래머스 3단계] 알고리즘 43. 거스름돈

---

 

이 문제는 0.5초 내에 풀어야 하고 메모리도 4메가바이트라, 1차원 배열만 사용할 수 있는 문제다.

 

게다가 문제에서도 같은 동전을 여러 번 사용해도 된다고 했다.

 

간단한 예시를 들면 정말 깔끔하게 풀린다.

 

1원 짜리, 2원 짜리, 3원짜리로 5원을 만드는 경우의 수를 구한다고 생각해보자.

 

문제를 푸는 과정은 이렇다. 

 

먼저 1원 짜리를 이용해 1원부터 5원까지 만드는 경우를 모두 구한다. 이후에 사용하기 위해서다.

각각 1가지다.

그 다음 1원 짜리와 2원 짜리를 이용해 1원부터 5원까지 만드는 경우를 구한다. 과정을 한 줄씩 살펴보자.

 

1원을 만들려고 하면 2원 짜리는 죽었다 깨도 못하므로 이전에 구했던 1원 짜리로 1원을 만드는 경우를 그대로 갖고 온다.

 

2원을 만들려고 하면 2원 짜리 하나로 가능하고, 이전에 구했던 1원 짜리로 2원을 만드는 경우도 된다.

1+1, 2 총 2가지다.

3원을 만들려고 하면 2원 짜리 하나 + 1원 짜리 하나와 이전에 구했던 1원 짜리로 3원을 만드는 경우다.

1+1+1, 2+1 총 2가지다.

...

핵심은 이전에 구했던 경우의 수와 현재 사용하기로 한 동전을 이용해 만드는 경우의 수를 합치는 것이다.

---

①원 짜리를 이용해 1원부터 5원까지 만드는 과정을 표를 이용해 정리하자면 다음과 같다.

	0원	1원	2원	3원	4원	5원
①	1	1	1	1	1	1
②
③

①원을 이용해 1원을 만드는 방법은 1가지다. 2원, 3원, 4원, 5원도 마찬가지다.

 

0원을 만드는 경우의 수는 1가지로 설정하는데, 이유는 1원을 만들기 위해 ①원 짜리를 하나 사용한다고 하면 남은 돈 0원을 만드는 경우의 수가 필요하기 때문이다. 

 

①원 짜리로 2원을 만들 때는 ①원 짜리 하나를 사용하고 남은 돈 1원을 만드는 경우의 수를 갖고 온다. 그리고 이전에 만들었던 경우의 수를 갖고 와야 하는데, 이전에 만든게 없으므로 넘어간다.

 

이제 ①원 짜리와 ②원 짜리를 이용해 1원부터 5원까지 만드는 과정을 정리해보자.

	0원	1원	2원	3원	4원	5원
①	1	1	1	1	1	1
②	1	1
③

②원 짜리로 1원을 만드는 경우는 없으니, 이전에 구했던 ①원 짜리로 1원을 만드는 경우의 수를 갖고 온다.

 

②원 짜리로 2원을 만드는 경우는 1가지다. 왜냐하면 ②원 짜리 하나를 사용하면 남은 돈 0원을 만드는 경우의 수를 갖고 와야 하는데, 이건 1가지라고 설정했기 때문이다. 거기에 이전 줄에서 구했던 2원을 만드는 경우의 수도 갖고 온다.

따라서 2가 된다.

	0원	1원	2원	3원	4원	5원
①	1	1	1	1	1	1
②	1	1	2
③

②원 짜리로 3원을 만드는 방법은 이전 줄에서 구한 경우의 수와 ①원 짜리와 ②원 짜리를 사용하는 방법을 더한 것이다.

 

이전 줄에서 구한 경우의 수는 1가지이고, 3원에서 ②원 짜리를 하나 사용하고 남은 돈 1원을 만드는 경우의 수는 1가지이므로, 3원을 만드는 경우의 수도 2가지다.

---

 

정리해보자면, N개의 동전 중에 i개의 동전을 사용해 K원을 만드는 경우의 수는,

i-1개의 동전을 사용해 K원을 만드는 경우의 수 + K원에서 i번째 동전의 값을 뺐을 때 남는 돈을 만드는 경우의 수다.

#include <iostream>
int main() {
    int dp[10001]{ 1 }, arr[101], N, K;
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 1; i <= N; i++) {
        for (int j = arr[i]; j <= K; j++) {
            dp[j] += dp[j - arr[i]];
        }
    }
    printf("%d", dp[K]);
}

 

 

장황하게 설명했지만 코드를 이해하면 정말 간단하다.