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

알고리즘 분류 (dp)

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

 

 

 

# 문제

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

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

 

 

# 예제

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

3 10
1
2
5

 

 

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

10

 

# 필요개념

n이 100 이하, k가 10000 이하이고, 시간 제한이 0.5초이기 때문에, 코드를 짤 때 O(nk) 선에서 끝내야했다. 이 점을 유의하고 코드를 짜기 시작했는데, 

 

틀린 풀이

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 = 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][n + 1];
        dp[0][0] = 1;
        for (int i = 0 ; i < n ; i++) {
            coin[i] = Integer.parseInt(br.readLine());
            dp[0][i + 1] = 1;
        }
        Arrays.sort(coin);

        for (int j = 1 ; j <= n ; j++) {
            int obj = coin[j - 1];
            for (int i = 1 ; i <= k ; i++) {
                for (int o = 0 ; o <= i / obj ; o++) { // obj의 개수
                    dp[i][j] += dp[i - (o * obj)][j - 1];
                }
            }
        }
        System.out.println(dp[k][n]);
    }
}

 

3초에서 시간초과가 발생한 코드이다. dp로 풀기 위해 (k + 1) * (n + 1) 크기의 이차원 배열을 선언했다. coin 배열을 오름차순으로 정렬해두고, 크기가 작은 동전의 경우의 수를 이차원 배열에 채워나갔다.

 

해당 문제의 예제에서

coin = 1인 경우 k가 1일때부터 10일때까지 모든 경우에서 k % coin == 0 을 만족한다. 이럴 때마다 dp[0][coin - 1]을 더해나갔다. 

 

그런데 만약 k가 10이고 coin이 5인 경우에는  

5가 들어가는 개수가 0, 1, 2로 나뉘게 되기 때문에 for문을 한 개 더 쓸 수밖에 없었다. 시간초과가 날 걸 예상했지만 역시나 정말 나버렸다. 그래서 고민하다가 2차원 배열이 아닌 1차원 배열을 만든 후, 그 위에 누적하는 방법을 선택했다.

 

정답 풀이

틀린 풀이와의 차이점은 dp[0][1] + dp[1][1] + dp[2][1] => dp[1] 로 합쳐졌다는거! 생각해보니 dp[all][coin - 1] 로 지정할 거라면, 굳이 이차원 배열로 만들 필요 없이 그 위에 누적하면 되는 것이었다

 

틀린 핵심코드 / 맞은 핵심코드

 

초반에 생각한대로 O(nk) 선에서 끝낼 수 있었다!

 

# Code

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

// 2293
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] coin = new int[n + 1];
        int[] dp = new int[k + 1];
        dp[0] = 1;
        for (int i = 0 ; i < n ; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(coin);

        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= k ; j++) {
                if (coin[i] > j) continue;
                dp[j] += dp[j - coin[i]];
            }
        }
        System.out.println(dp[k]);
    }
}

 

 

# 결과