백준 2293 동전1

문제

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

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

입력

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

출력

 

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

 

예제 입력  

3 10 1 2 5

예제 출력 

10

 

접근

• Dynamic Programming으로 접근한다.

• 첫 번째 동전만 사용하여 각 k값 마다 가능한 경우의 수를 찾는다.

• 첫 번째~두 번째 동전만 사용하였을 때, 각k 값 마다 가능한 경우의 수를 찾는다.이 때, 첫 번째 동전만 사용해서 구했던 경우의 수를 활용한다.

• 첫 번째~n 번째 동전을 사용하였을 때까지 반복한다.

예시

 

1, 2, 5만을 이용하여 10을 만들어야 한다.

 

1원만 사용하여 위의 가격을 만들 때, 당연히 죄다 경우의 수는 한개밖에 나오지 않는다.

 

2원을 추가로 사용하여 위의 가격을 만든다고 할 때,

 

 

이런 표가 완성 될 것이다.

 

설명을 덧 붙이자면,

 

아까 미리 구해뒀던 1의 경우의 수를 활용한다고 했다.

이제 규칙을 찾는 것이다.

 

Mn[j]를 n의 동전을 포함하여 j가격을 만들 수 있는 경우의 수라고 할때,

M2[i] = M1[i] + M2[i-2]라는 규칙이 보인다.

 

이 말은 즉, 현재 동전을 추가한다고 할 때, 추가하기 전 금액의 경우의수를 

구해서 더해준다는 말. 

(예를 들어 M2[4]를 구하려면 M2[2]와 M1[4]를 더하면 된다는 것)

 

위를 구현하면 2차원 배열을 사용하게 되는데, 문제에서 주어진 메모리 크기는 4MB다.

 

2차원 배열을 쓰기엔 크기가 적어서 1차원 배열로만 해결을 해야한다. 

 

그렇다면,  그냥 현재 구하고 있는 동전값을 빼준 인덱스를 가지고 있는 dp값을 계속 더해주기만 하면 된다

 

소스

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[n];
        int[] dp = new int[s+1];
        
        for(int i = 0 ; i < n ; i++) {
            coin[i] = in.nextInt();
        }
        
        dp[0] = 1; //최초 시작점
        for(int i = 0 ; i < n ; i++) {
            for(int j = 1 ; j <= s ; j++) {
                if(j - coin[i] >= 0) dp[j] += dp[j - coin[i]];
            }
        }
        System.out.println(dp[s]);
    }
}