2293번, 2294번 - 동전1,2(규칙성 찾기)

2293 - 동전1

주어진 동전들로 값 k를 만들 수 있는 경우의 수를 구하는 문제이다.

처음에는 재귀를 이용해 해당 값을 만들 수 있는 모든 경우의 수를 구했다,.

하지만 재귀는 너무 비효율적이였고, 값이 커질수록 너무도 많은 시간이 필요했다.

import java.util.*;

public class 동전1_2293번_시간초과 {
    static int n, k;
    static int count = 0;
    static int[] coins;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        coins = new int[n];
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            queue.add(sc.nextInt());
        }

        for (int i = 0; i < n; i++) {
            coins[i] = queue.poll();
        }

        recursion(n-1, 0);

        System.out.println(count);
    }

    static void recursion(int temp, int sum) {
        if (temp < 0) {
            return;
        }
        while (sum < k) {
            recursion(temp-1, sum);
            sum += coins[temp];
        }
        if (sum == k) {
            count++;
        }
    }
}

구글링을 하여 힌트를 얻었고, 몇번 적어보는 것이 중요할 것 같았다.

목표는 9원, 가진 동전은 1원, 2원, 6원 이라고 가정해보자.

1원으로는 9원까지의 모든 가격을 만들 수 있다.

2원을 포함하여 만들 수 있는 경우의 수도 생각해보자 

어라라..? 뭔가 규칙이 있는듯 하다.

6원도 한번 고려해보자

이러니까 확실한 규칙이 보인다. 0을 추가하면 더 확실해질 것이다.

1. 현 동전(c) 가격 이상의 값만 고려하면 된다.

2. i번째 가격을 만들 수 있는 경우의 수 += 지금(i) - c 번째 가격을 만드는 경우의수

 

이 두가지만 고려하면 된다.

그 결과 나온 코드는 다음과 같고, 규칙성을 고려한 풀이이기에 재귀를 이용한 풀이보다 훨씬 빠른 속도를 가진다.

import java.util.*;

public class 동전1_2293번 {
    static int n, k;
    static int count = 0;
    static int[] coins;
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

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

        for (int i = 0; i < n; i++) {
            coins[i] = sc.nextInt();
        }

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

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

 

 

2294 - 동전2

주어진 동전들로 값 k를 만들 수 있는 동전의 최소 개수를 구하는 문제이다.

이 또한 위의 문제와 크게 다르지 않은데, 한번 그려보면 알 수 있다.

목표값은 12원이고, 1원, 4원, 9원이 있다고 가정하자.

 

1. 어떤 경우도 목표값 + 1보다 큰 동전의 개수를 요구하지 않으니 아래와 같이 표를 채워넣는다.

 

2. 1원으로 각 가격들을 만들 수 있는 최소 개수는 각 가격과 같다. 이는 모두 13보다 작으니 값을 바꿔준다.

 

3. 4원으로 각 가격들을 만들 수 있는 동전의 최소 개수는 4부터 고려한다.

뭔가.. 규칙이 있는 것 같다. 9원도 한번 보자.

 

4. 9원도 고려해본다.

12원을만들 수 있는 경우의 수는 변경되지 않았다.

그래도 일정한 규칙성이 이제는 보일 것이다.

 

3, 4번 과정에 0을 추가해보겠다.

4원에서 더 도드라지게 나타나는데, (0,1,2,3), (1,2,3,4), (2,3,4,5), (3)이 보인다.

4원에서는 자신보다 4칸 앞쪽에 있는 값 + 1이 반복되고 있다고 해석할 수 있다.

하지만 9원 포함시 마지막 부분이 (1, 2, 3, 4)가 아닌 (1, 2, 3, 3)이 되고 있는 것을 볼 수 있는데,

4원까지만 포함시킨 과정에서 최솟값이 3이기 때문이다.

 

위 해석을 고려해서 코드를 작성하면 다음과 같다.

import java.util.*;

public class 동전2_2294번 {
    static int n, k;
    static int min;
    static int[] coins;
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        min = k+1;
        coins = new int[n];

        for (int i = 0; i < n; i++) {
            coins[i] = sc.nextInt();
        }

        dp = new int[k+1];
        Arrays.fill(dp, k+1);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]]+1);
            }
        }

        if (dp[k] > k) {
            System.out.println(-1);
        } else {
            System.out.println(dp[k]);
        }
    }

}

 

동전 1,2를 풀며 얻은 교훈은 문제에 규칙이 존재하는지 확인하는 것이 중요하다는 점이다.

정말 이건 무조건 재귀다! 말고는 재귀를 좀 지양해보자..