[백준]2293번 동전1 ( 나중에 다시 풀어볼 것 )

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다.

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

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

• n 가지 종류의 동전을 사용해서 k 를 만드는 것.

종류는 최대 100가지

합인 k 는 최대 1만.

동전의 가치는 10만 이하의 자연수

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. —> 따라서 각 경우에 대한 동전의 개수에 따라 경우에 대한 유일성을 부여해야할 듯 하다.

문제풀이

오랜만에 푸니 정말 안 풀린다.

• 각 가치에 대한 동전 개수의 경우의 수로 풀면, 각각 2가지 경우가 있다고만 해도 2^ 100 이 된다.

개수로 풀려고만 생각하니 도무지 생각이 안난다.

• 금액으로 접근해 볼 수 없을까????

다른 사람 풀이를 보았다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class Main {

	public static int n ;
	public static int k ;

	// 연산의 수 : 최대 10000 x 100 => 100만
	public static int[] dp = new int[10001];
	public static int[] c = new int[101]; // 코인의 가치
	
	// 이 코드는 무시 ( 템플릿처럼 사용중인 입출력 코드 _제네릭,함수형인터페이스 연습용 ) 
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer st;
	public static Parser<Integer> parser = new Parser<Integer>(str -> Integer.parseInt(str));

	static class Parser<T>{
		Function<String, T> func;

		public Parser(Function<String, T> func) {
			this.func = func;
		}

		public T parseToNumeric(String str){
			return func.apply(str);
		}
	}
	// ============================

	public static void setUp() throws IOException {

		st = new StringTokenizer(br.readLine());
		n = parser.parseToNumeric(st.nextToken());
		k = parser.parseToNumeric(st.nextToken());

		for(int i =0;i<n;i++){
			c[i] = parser.parseToNumeric(br.readLine());
		}

		dp[0] =1 ;
	}

	public static int solve(){
		// coin 은 index 0 부터 들어가 있음
		for(int i =0 ; i<n;i++) {
			// dp 는 만들어야 하는 가치를 index 로 담는 것으로 하기에 1 ~ k 까지 돌아갈 것임
			// 이 때, 조금이라도 연산을 줄이기 위해서는, 현재 코인의 가치보다 작은 경우는 dp[x] 에 추가되는 경우의 수가 없기 때문ㅇ
			// c[i] 부터 시작하는 것으로 할 수 있다.
			for(int x = c[i]; x <= k; x++){
				dp[x] += dp[x-c[i]];
			}
		}
		return dp[k];
	}

	public static void main(String[] args) throws IOException{
		setUp();
		System.out.println(solve());
	}
}