백준 9084 (동전) <배낭 문제>

문제

9084번: 동전

n개의 서로 다른 금액의 동전이 주어지면 동전을 조합해서 m의 금액이 나올 수 있는 경우의 수를 구하는 문제이다.

예를 들어 n은 3이고 서로다른 동전은 2, 3, 5라고 할 때 m = 10이면 정답은 4가 된다. {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5}

---

여러 규칙을 찾으려 노력했지만 이러한 문제 유형은 배낭 문제이다.

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

위에 예시를 기반으로 표를 만들면 다음과 같다.

이를 코드로 구현하면 아래와 같다.

int []dp = new int[m+1];
dp[0] = 1;

for(int i=0;i<n;i++){
	for(int j=coin[i];j<=m;j++){
    	dp[j] += dp[j - coin[i]];
    }
}

---

전체 코드이다.

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 t = Integer.parseInt(st.nextToken());
        while(t-- > 0){
            st = new StringTokenizer(br.readLine());
            int n  =Integer.parseInt(st.nextToken());

            int[]coin = new int[n];

            st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++){
                coin[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());

            int []dp = new int[m+1];
            dp[0] = 1;

            for(int i=0;i<n;i++){
                for(int j=coin[i];j<=m;j++){
                    dp[j] += dp[j - coin[i]];
                }
            }
            System.out.println(dp[m]);
        }
    }
}