[Gold IV] 동전 1 - 2293

문제 링크

성능 요약

메모리: 18224 KB, 시간: 128 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 4월 19일 22:09:10

문제 설명

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

구하고자 하는 것

n개의 동전을 사용하여 k원을 만드는 경우의 수를 구하고 싶다

풀이 설계하기

기본에 맞춰 백트래킹을 통한 완전 탐색부터 고려하면, 동전의 수는 최대 100개이다.
따라서 2의 100승이므로 백트래킹으로는 해결할 수 없다.

따라서 O(N^3)이 100만이므로, 이보다는 나은 시간 복잡도로 문제를 해결해야 한다.
이전의 배낭 문제와 벼락치기 문제처럼, 이전의 상태를 바탕으로 새 문제를 해결할 수 있는 dp로 접근해 보자.
우선 점화식을 세우면

점화식 설계하기

동전이 1, 2, 3원이 있고 7원을 만드는 경우를 살펴보자.
1원으로는 0원부터 7원까지 모두 만들 수 있으나, 가지수는 모두 1가지뿐이다.

여기에 2원도 사용하여 만든다 가정하자. (1, 2원짜리 동전 사용)
그러면 1원까지는 이전의 1원으로 만드는 방법밖에 없으나 2원부터는 (2, 1 * 2) 두 가지로 만들 수 있다.
3원은 (1 x 3, 1원과 2원) 두 가지로 만들 수 있다.
4원은 (1 x 4, 1 x 2 + 2 x 1, 2 x 2) 세 가지로 만들 수 있다.
5원은 (1 x 5, 1 x 3 + 2 x 1, 2 x 2 + 1 x 1) 세 가지로 만들 수 있다.
6원은 (1 x 6, 1 x 4 + 2 x 1, 2 x 2 + 1 x 2, 2 x 3) 네 가지로 만들 수 있다.

내가 종이로 써 보며 할 때에는 3원까지 써서 내린 결론이나, 편의상 2원까지 시뮬레이션 한 것으로 점화식을 설명한다.

2원마다 하나씩 가지수가 증가하는 것을 볼 수 있다.
왜냐하면, 2원은 (1원 동전 하나로 만들 수 있는 2원 가지수 + 0원(2원 - 2원(동전가치))을 현재 동전 2원으로 만들 수 있는 가지수)고

4원은 (1원 동전 하나로 만들 수 있는 4원 가지수 + 2원(4원 - 2원(동전가치))을 현재 동전 2원으로 만들 수 있는 가지수)이다.

이전 동전 가지수로 만들 수 있는 k원 + 현재 동전 가지수로 만들 수 있는 k-coin(현재동전금액) 가지수가 나타난다.

따라서 이를 식으로 나타내면

• 이전 종류의 동전으로 j원을 만드는 가지수는 현재 동전들로 j원 만드는 방법 이하이다(dp[i][j] = dp[i-1][j])
• 그리고 이전 동전들로 j원을 만드는 수 + 현재 동전들로 j-coin원을 만드는 수를 더하면 된다.

최종 점화식은

dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j] + dp[i][j-coin]) (if(j >= coin))

이 된다.

시간복잡도 살펴보기

동전 개수인 N만큼 루프를 돌며, 각 루프마다 1원부터 M원까지 탐색한다.
따라서 O(NM)이고, 100만 정도이기에 충분히 문제를 해결할 수 있다.

정답 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] coins = new int[N];

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

        int[][] dp = new int[N+1][K+1];
        dp[0][0] = 1;   // 0원을 만드는 법은 1가지

        for (int i = 1; i <= N; i++) {
            int coin = coins[i-1];  // 현재 동전의 금액
            dp[i][0] = 1;

            for (int j = 0; j <= K; j++) {
                dp[i][j] = dp[i-1][j];  // i개째 동전을 고르지 않더라도 i-1개로 만든 j원 가짓수는 유지된다

                if(j >= coin){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j] + dp[i][j-coin]);
                }
            }
        }

        System.out.println(dp[N][K]);
    }
}

이 외에도 백준의 3067번, 9084번 등이 문제 번호만 다르다시피 한 거의 같은 문제이다.
합법적 어뷰징(?)인지는 모르겠으나 한 문제를 풀고 다른 문제들을 복습삼아 풀면 좋다.
아무튼 추론과 증명을 통한 이해보다는 직접 시뮬레이션을 통해 속칭 몸으로 문제를 푼 감이 있어서, 다른 증명이 있으면 추가로 적어 보려 한다.