백준_동전1_2293

//알고리즘

1. dp

-> n x k 의 dp 테이블 생성

-> k값 1~k까지 n으로 만들 수 있는 경우의 수를 저장

-> dp[i][j]에 저장되는 값 : 

 num[i]값을 제외하고 만들 수 있는경우(dp[i-1][j]) + num[i] 값으로 만들 수 있는 경우(sum)

 

dp 문제를 많이 안 풀어봐서 코드는 간단하지만 시간은 오래걸림...

 

import java.util.Scanner;

public class 동전1_2293 {
	static int n, k, num[], dp[][];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();

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

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

		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= k; j++) {
				int sum = 0;
				int l = j;
				while (true) {
					if (l - num[i] < 0) {
						break;
					}
					l -= num[i];
					if (dp[i - 1][l] > 0) {
						sum += dp[i - 1][l];
					}

				}
				dp[i][j] = sum + dp[i - 1][j];
			}
		}

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

	}

}

 

※ 수정 : dp 테이블을 1차원 배열로 만들어서 풀면 더 쉬움.

 

package baekjoon;

import java.util.Scanner;

public class 동전1_2293 {
	static int n, k, num[], dp[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();

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

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

		dp[0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= k; j++) {
				if (j >= num[i]) dp[j] += dp[j - num[i]];
			}
		}

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

	}

}