[백준] 2293 : 동전 1 (JAVA)

난이도

🥇 5

 

링크

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

2293번: 동전 1

---

문제

---

풀이과정

해당 문제는 DP를 사용하는 문제이다.

 

처음에 조합을 사용해서 문제를 풀어보려고 하기도 했지만 순서만 다른 경우도 포함되어 어떻게 문제를 풀어야 되나 고민을 하였다. 

순서만 다르고 조합이 같은 경우를 중복시키지 않기 위해선

➡️ 원하는 값이 나올 때까지 사용할 수 있는 동전의 수를 메모이제이션 하면 되는 것이다!

 

 

문제에서 주어진 예시를 들어 설명해보자면

3가지 종류의 동전 (1, 2, 5)을 가지고 10원이 되도록 만들 수 있는 경우의 수를 구하는 것이다.

 

그렇다면 우선 1원 동전을 가지고 10원을 만들 수 있는 경우의 수를 구해보도록 하면

	1	2	3	4	5	6	7	8	9	10
coin[0] = 1	1	1	1	1	1	1	1	1	1	1

 

위와 같은 결과가 나온다.

1원을 만드려면 1원 동전 1개가 필요하고, 2원을 만드려면 1원 동전 2개가 필요하고, ...

10원을 만드려면 1원 동전 10개가 필요하여

즉, 10원을 만들기 까지 1원 동전이 필요한 경우의 수는 모두 1가지 인 것이다.

 

그렇다면 2원 동전을 추가하여 10원을 만들 수 있는 경우의 수를 구해보자면

	1	2	3	4	5	6	7	8	9	10
coin[0] = 1	1	1	1	1	1	1	1	1	1	1
coin[1] =2	1	2	2	3	3	4	4	5	5	6

 

위와 같이 나온다.

1원을 만드려면 1원 동전 1개가 필요하고, 2원을 만드려면 1원 동전 2개 혹은 2원 동전 1개가 필요하고, 

3원을 만드려면 1원 동전 3개 혹은 2원 동전 1개, 1원 동전 1개가 필요하다.

이러한 과정을 10원까지 반복하면 1원과 2원을 가지고 10원을 만들 수 있는 경우의 수는 6가지가 만들어진다.

 

그렇다면 마지막 5원 동전을 추가하여 10원을 만들 수 있는 경우의 수를 구해보면

	1	2	3	4	5	6	7	8	9	10
coin[0] = 1	1	1	1	1	1	1	1	1	1	1
coin[1] =2	1	2	2	3	3	4	4	5	5	6
coin[2] =5	1	2	2	3	4	5	6	7	8	10

 

위와 같은 결과가 나온다.

이전 과정을 생략하고 5원을 만들기 위해 1원 동전 5개 / 1원 동전 3개와 2원 동전 1개 / 1원 동전 1개 2원 동전 1개 / 5원 동전 1개가 필요하다. 

이러한 과정을 10원까지 반복한다면 1원 동전, 2원 동전, 5원 동전을 가지고 10원을 만들 수 있는 경우의 수는 총 10가지가 되는 것이다.

 

이때 파란색으로 칠한 부분을 자세히 살펴보면 N원 동전이 추가될 때마다 dp[N] 부분에 +1이 되는 것을 살펴볼 수 있다.

즉, N원이 만들어지기 위해 사용할 수 있는 동전의 수가 +1 되는 것이다.

 

위의 설명을 통해 얻을 수 있는 점화식은

k원을 만들고자 하는 경우 k >= coin[i] 라면, dp[k] = dp[k] + dp[k - coin[i]]로 표현할 수 있다.

 

 

예시를 추가해보면 

3가지 종류의 동전 (2, 3, 5)을 가지고 10원이 되도록 만들 수 있는 경우의 수를 구하고자 할 때 아래 결과가 나온다.

	1	2	3	4	5	6	7	8	9	10
coin[0] = 2	0	1	0	1	0	1	0	1	0	1
coin[1] =3	0	1	1	1	1	2	1	2	2	2
coin[2] =5	0	1	1	1	2	2	2	3	3	4

 

이전의 예시와는 달리 2원을 가지고는 2의 배수인 2원, 4원, 6원, 8원, 10원 만을 만들 수 있기 때문에 홀수인 경우는 0가지가 된다!

이 점을 고려하여 점화식을 사용해 이후의 과정을 반복한다면 총 4가지의 경우의 수가 나온다는 것을 확인할 수 있다.

 

🚨 dp를 하기 전에 dp[0] = 1로 설정하는 거 잊지 말기! ( k = coin[i] 일 때, 사용할 수 있는 동전의 수가 +1 되는 것 반영하기 위해!)

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] coin = new int[n];
        int[] dp = new int[k+1];

        for (int i = 0; i < n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }

        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                if (j >= coin[i]) {
                    dp[j] += dp[j - coin[i]];
                }
            }
        }

        System.out.println(dp[k]);
    }
}

 

결과