[Algorithm] 동전1

이번 문제는 굉장히 어려웠다. 어떤 동전의 값을 만드는 경우의 수를 구하는 문제였는데

이런 문제는 사실 DP로 1원,2원,5,원이 있으면 C[N]에 대한 점화식을 C[N-1],C[N-2],C[N-5]

등등으로 구해서 문제를 푸는 방식으로 해결했는데 , 위와같은 방법으로 문제를 해결하려고

하니 1+1+1 , 1+2 , 2+1 등 동전의 갯수는 변함이 없는데 다른 경우로 counting되는

경우가 생겨서 한참을 고민했다.

이번 문제는 해설을 참고하여 코드를 작성하였다.

방법은 위와 조금은 비슷하지만 출발 선이 달랐었다. 바로 주어진 동전 (1,2,5)등을 이용해

차례차례로 N까지의 경우의 수를 축척시켜가는 것이였다.

N = 10인 경우 1원 만을 사용하여 만드는 경우는 1가지 씩이 될 것이다.

두번째로 2원을 사용하여 만드는 경우는 N = 1 ~ 10 에 대하여 N-2 경우 , 5원을

이용하여 만드는 경우는 N = 1 ~ 10 에 대하여 N-5인 경우에 각각 축척 시켜나간다.

이러한 것을 전혀 생각못했다 . 아직 내가 멀었음을 느낄 수 있는 문제였다.

전형적인 DP문제만 해결 할 줄 알지만 이런 다양한 문제들을 더 많이 풀어봐야겠다.

소스코드:

package algorithm;

import java.io.*;
import java.util.StringTokenizer;

public class a_2293 {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] d = new int[k + 1];
d[0] = 1;

for (int i = 0; i < N; i++) {
int t = Integer.parseInt(br.readLine());
for (int j = t; j <= k; j++) d[j]+=d[j-t];
}
System.out.println(d[k]);
}

}