[JAVA] 백준 2293번

https://www.acmicpc.net/problem/2293 동전 1 -다이나믹 프로그래밍

[백준 2293번] 동전 1

예제를 풀어 봄

문제 파악 해서 정리 해 봄:

n개의 숫자 조합을 이용해 합 k를 맞추는 경우의 수를 찾는 문제. (순서 상관없고, n개 다 이용 안 해도 됨, 동전 중복 사용 가능)

풀이 생각해 봄: dp

1원부터 생각->1,2원 두가지 동전 종류가 있을 때 생각 -> 1,2,3원 세 가지 동전 종류가 있을 때 생각

~

이 과정에서 규칙을 발견하고 점화식 세워보기

코드 짜기.

출처 https://songsunbi.tistory.com/67

하나 더 고려해야 할 점이 있습니다. 3원으로 경우의 수를 계산하는데 1원과 2원의 경우를 계산할 필요가 있을까요?

어차피 제가 가지고 있는 동전은 3원이기 때문에 1원과 2원은 생각할 필요도 없게 되는 것입니다.

	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
2원	0	1	0	1	0	1	0	1	0	1
3원	생각할 필요도 없 0	생각할 필요도 없 1	1	1	1	2	1	2	2	2
5원	생각할 필요도 없 0	생각할 필요도 없 1	생각할 필요도 없 1	생각할 필요도 없 1	2	2	2	3	3	4

코드:

package till;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int s = in.nextInt();

        int[] coin = new int[101];//인덱스 번호 1부터 직관적으로 시작하려고 +1씩 해서 배열 선언
        int[] dp = new int[10001];

        for(int i = 1 ; i <= n ; i++) {
            coin[i] = in.nextInt();
        }

        //i는 x번째->coin[x번째 동전 종류]의 경우를 의미
        //j는 i의 동전 종류로 1~s원를 채우는 경우의 수를 의미
        dp[0] = 1; //최초 시작점
        for(int i = 1 ; i <= n ; i++) {
            for(int j = coin[i]; j <= s ; j++) {
                dp[j] += dp[j - coin[i]];
                /*
                 * 다음으로, 3원짜리 동전이 저에게 있다고 가정합니다. 
3원짜리 동전으로 3원은 1가지지만 6원은 2+2+2와 3+3 2가지의 경우가 존재합니다. 
여기서 동적 프로그래밍의 개념이 나옵니다. 
이전의 경우를 저장해놓고, 현재의 경우와 이전의 경우를 합해 나가면서 경우의 수를 계산합니다.
즉, 6원을 만드는 경우의 수를 계산할 때, 2원짜리로 6원을 만들 수 있는 경우의 수와 3원짜리로 6원을 만들 수 있는 경우의 수를 합해야 한다는 의미입니다. 
                 */
            }
        }

        System.out.println(dp[s]); 

    }
}