Java

[백준 2293] 동전1 (JAVA)

iheeeee6-6 2023. 2. 7. 16:46
728x90

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

 

2293번: 동전 1

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

www.acmicpc.net

 

점화식 dp[j] = dp[j] + dp[j-i번째 동전값]

 dp[j]는 j원이 될 수 있는 경우의 수를 뜻한다.

 

1) i=1 

dp[1]=dp[1]+dp[1-1]; -> 1

dp[2]=dp[2]+dp[1]; -> 1

.

.

dp[10]=dp[10]+dp[10-1]; ->1

 

2) i=2

dp[2]=dp[2]+dp[2-2]; -> 2

dp[3]=dp[3]+dp[3-2];->2

dp[4]=dp[4]+dp[4-2]; ->1+2 = 3

.

.

.

 

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

public class Main {
	static int[] arr, dp;
	static int num, sum;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		num = Integer.parseInt(st.nextToken());
		sum = Integer.parseInt(st.nextToken());
		arr = new int[num + 1];
		dp = new int[sum+1];
		for (int i = 1; i < num + 1; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		dp[0]=1;
		for (int i = 1; i < num + 1; i++) {
			for (int j = arr[i]; j <= sum; j++) {
				dp[j]=dp[j]+dp[j-arr[i]];
			}
		}
		System.out.println(dp[sum]);
	}

}

'Java' 카테고리의 다른 글

[백준 1697] 숨바꼭질 (JAVA)  (0) 2023.02.08
[백준 1309] 동물원 (JAVA)  (0) 2023.02.08
[백준 2133] 타일 채우기 (JAVA)  (0) 2023.02.05
[백준 1439] 뒤집기 (JAVA)  (0) 2023.02.04
[백준 1202] 보석도둑 (JAVA)  (0) 2023.02.03