[BOJ]2293_동전1_Java

--문제--

https://www.acmicpc.net/problem/2293

2293번: 동전 1

--문제 접근--

처음 문제를 봤을 때 중복 조합을 만들어 K를 만든다면 +1을 하여 답을 구하려 했는데 시간 초과가 나타났습니다.

다시 조건을 보니 당연한 시간 초과였습니다..

그리하여 다르게 생각해본 결과 DP를 통해 문제를 푸는 방법을 고려하였습니다.

 

1.dp배열을 만듭니다.

2.dp [금액]=금액을 만드는데 가능한 경우의 수

3. dp [i]=dp [i]+dp [i-coin]입니다.

N은 2로 하고 K는 5 로 가정해서 해보겠습니다.

맨 처음 dp [0]=은 1 로 가정하고 시작합니다. 그래야 진행할 수 있습니다.

2 5

1

2

1원을 통해 만드는 dp값

1	2	3	4	5
1	1	1	1	1

2원을 통해 만드는 dp값

1	2	3	4	5
1	1(원래dp[2])+1(dp[2-2(coin)]=2	1+1(dp[3-2(coint)]=2	3	3

dp [i]=dp [i]+ dp [i-coin]

--코드--

package 기초백준추천문제;

import java.util.Scanner;

public class BOJ_2293_동전1 {
	//문제접근
	//처음에는 중복조합을 만들어 K를 만든다면 1+를 하여 답을 구하려했는데 시간초과가 나타났다.
	// 다른방법을 고려해야하는데..
	static int[] num;
	static int N,ans,K;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		K=sc.nextInt();
		num=new int[N];
		int[] arr=new int[N+1];
		int[] dp=new int[K+1];
		dp[0]=1;
		for(int i=1;i<=N;i++) {
			arr[i]=sc.nextInt();
			for(int j=arr[i];j<=K;j++) {
				dp[j]+=dp[j-arr[i]];
			}
		}
		System.out.println(dp[K]);
		//아래는 중복조합
//		for(int i=0;i<N;i++) {
//			num[i]=sc.nextInt();
//		}
//		ans=0;
//		DFS(0,0,0);
	}
	
	
	//중복조합구하는가정
//	private static void DFS(int idx, int start, int tmp) {
//		if(tmp>=K) {
//			if(tmp==K)ans++;
//			return;
//		}
//		for(int i=start;i<N;i++) {
//			DFS(idx+1,i,tmp+num[i]);
//		}
//		
//	}

}