백준 2293번 :: 동전 1 (DP)

www.acmicpc.net/problem/2293

2293번: 동전 1

📌동적 프로그래밍(Dynamic Programming)

 

- dp 문제는 이전의 구한 값을 통해 현재 원하는 값을 도출하는 방식

- 중복하는 값이 있다면 제외하고 풀면 된다.

- 만들고 싶은 value(=여기선 금액)을 기준으로 한다.

 

📌문제 풀이

• 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
• dp[] 배열을 선언한다.
• dp[i] = j 라고 하면, 
  • i = 금액
  • j = i원을 만드는데 가능한 경우의 수
• dp[i] = dp[i] + dp[i-coin]
  • 1원 짜리 동전으로 1원부터 10원까지 만들 수 있는 가짓수
  • 2원 짜리 동전으로 2원부터 10원까지 만들 수 있는 가짓수
  • 5원 짜리 동전으로 5원부터 10원까지 만들 수 있는 가짓수를 구한다. 

 

예제인 10원을 만들기 위한 1, 2, 5에 대한 표는 아래와 같다.

• 1원 짜리 동전으로 1원부터 10원까지 만들 수 있는 가짓수
• 2원 짜리 동전으로 2원부터 10원까지 만들 수 있는 가짓수
• 5원 짜리 동전으로 5원부터 10원까지 만들 수 있는 가짓수를 구한다. 

	1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1원	1	1	1	1	1	1	1	1	1	1
2원	0 총 1가지	1 총 2가지	1 총 2가지	2 총 3가지	2 총 3가지	3 총 4가지	3 총 4가지	4 총 5가지	4 총 5가지	5 총 6가지
5원	0	0	0	0	1	1	2	2	3	4
Total		2	2	3	4	5	5	7	8	10

 

- 2원짜리 동전으로 3원 만들기

• 3원에서 2원을 빼면 1원인데, 1원에서 구했던 경우의 수에 단지 2원의 coin만 추가하면 3원을 나타낼 수 있다.
• 이 때 1원에서 현재까지 구했던  총 경우의 수는 1가지이므로 이 때의 경우가 그대로 1가지로 들어온다.
• 1원1원 의 경우의 수가 => 2원 3원의 경우의수로 그대로 온다 (=1가지)

- 2원짜리 동전으로 4원 만들기

• 4원에서 2를 빼면 2원
• 2원의 경우의 수에 2원 하나만 그대로 얹으면 되는거니깐 2원의 경우의 수만큼 값이 들어가면 된다.

- 5원에서 2원을 뺀 3원의 경우의 수가 그대로 들어오면 된다. 3원에 그대로 2만 더하면 되는거니까

- 7원에서는 5원의 경우의 수가 그대로 오면 된다.

 

 

DP연습 열심히 해야겠다 어려우ㅠㅠ 

 

🎈소스코드

 

package BaekJoon.DP;

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

public class Q2293_동전1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int[] coin = new int[101]; // 동전의 가치 1, 2, 5
		int[] dp = new int[100001];

		int N = Integer.parseInt(st.nextToken()); // 1<=N<=100
		int K = Integer.parseInt(st.nextToken()); // 1<=K<=10,000

		for(int i=1; i<=N; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}

		dp[0] = 1;
		for(int i=1; i<=N; i++) { // 1원 2원 5원으로 10원 만들기
			for(int j=coin[i]; j<=K; j++) {
				dp[j] = dp[j] + dp[j-coin[i]];
			}
		}

		System.out.println(dp[K]);
	}
}