백준 2293 [자바] java 동전 1

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

2293번: 동전 1

▶문제

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

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

---

▶입력

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

---

▶출력

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

---

▶해설

합이 k원이 되는 경우의 수를 구하는데 주어진 조건을 보겠습니다.

1. 각각의 동전의 몇 개라도 사용 가능 -> 같은 동전을 여러 번 사용해도 됩니다.

2. 사용한 동전이 구성이 같다면 순서 상관없이 같은 경우 -> 4원을 만드는데 (1, 1, 2), (2, 1, 1)(1, 2, 1) 같은 경우

 

예를 보겠습니다. 

동전은 1원 2원이 존재하며, 6원을 만들 수 있는 경우의 수를 구해보겠습니다.

 

1원을 만들 수 있는 경우의 수

▶ 1

 

2원을 만들 수 있는 경우의 수

▶ (1,1), 2

 

3원을 만들 수 있는 경우의 수

▶(1,1,1), (2,1)

 

4원을 만들 수 있는 경우의 수

▶(1,1,1,1), (2, 2), (1,1,2)

 

~생략

 

예시를 살펴보겠습니다.

arr[1] = 1원, arr [2] = 2원

2원 -> 1원+1원 || 0원+2원 dp [2]

3원 -> 1원+1원+1원 || 2원+1원 dp [3]

4원 -> 1원+1원+1원+1원 || 2원+2원 || 1원+1원+2원 dp [3]

 

이를 토대로 3원이 되기 위해선 현재 동전의 가치를 뺀 것의 배열 값을 더해주면 됩니다.

▶ dp [3] += dp[3-arr[2]] -> dp[3] += dp [1]로 k까지 구해주시면 됩니다. 

 

따라서 아래의 점화식을 만족합니다.

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

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n,k;
    static int [] arr,dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);

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


        for(int i=1; i<=n; i++){
            String s1 = br.readLine();
            arr[i] = Integer.parseInt(s1);
        }

        dp[0]=1;


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

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