[백준 스터디 8주차] 9084번 동전 골드5 - 자바(JAVA) / 경우의 수를 구하는 DP

📑 문제

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

9084번: 동전

문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

출력

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

 

 

 

 

 

 

✒️ 풀이

 이 문제는 "경우의 수"를 구하는 문제임을 유의해야 한다. 차근차근 접근하니 겨우 이해됐다.

 

 

 

 먼저 이 개념을 이해해야 한다.

 🔔 특정 동전을 "써야한다"는 것은, (특정 동전을 안 쓴 금액)에 (특정 동전)을 써서 (목표 금액)을 만든다는 뜻이다.

 즉, (목표 금액-특정 동전 금액)을 만드는 경우의 수에 (특정 동전)를 쓰는 케이스가 추가되는 것이다. 

 

 

 

 ➡️ 위 개념을 가지고 아래 예시를 살펴보자.

 1원을 가지고 1원을 만드는 경우의 수는 한 가지이다. 1원보다 작은 동전은 없기 때문에, 1원 딱 하나를 쓰는 경우의 수 1개만이 존재한다.

 

 ❗ 이때, 2원을 가지고 3원을 만드는 경우의 수를 생각해보자.

 위에 주의한 개념을 생각해보면, (목표금액 3원-특정 동전금액 2원)인 1원을 만드는 각 경우의 수에 (특정 동전 2원)을 쓰는 케이스만 추가된다.

 따라서 2원을 가지고 3원을 만드는 경우의 수는, 1원을 만드는 한 가지 경우{1원}에 2원이라는 케이스만을 추가한 한 가지 경우{1원, 2원}가 된다.

 

 ❗ 조금 더 응용하여, 2원과 4원을 가지고 4원을 만드는 경우의 수를 생각해보자.

 ✔️ 먼저 제일 작은 동전 2원부터 목표금액 4원까지 만들어 본다. 2원을 가지고 2원을 만드는 경우의 수는 1가지이다.

 

 ✔️ 다음, 2원을 가지고 목표금액 3원을 만드는 경우는 (3-2, 1원을 만드는 경우의 수)에 (2원이라는 케이스)를 추가한 것이다. 1원을 만드는 경우의 수는 0가지이므로(현재 가지고 있는 동전은 2원과 4원밖에 없다), 2원을 가지고 3원을 만드는 경우도 0가지이다.

 

 ✔️ 다음, 2원을 가지고 목표금액 4원을 만드는 경우는 (4-2, 2원을 만드는 경우)의 수에 (특정 동전 2원)을 추가한 것이다. 최종 2원을 만드는 경우의 수는 {2원} 1가지이므로, 여기에 목표금액 4원을 만들기 위해 동전 2원을 추가하면 (2원을 가지고 4원을 만드는 경우의 수)는 {2원, 2원} 한 가지가 된다. 따라서 0으로 초기화 되어있는 dp[4](주어진 동전으로 4원을 만들 수 있는 경우의 수)에는 1이 저장이 된다.

 

 ✔️ 마지막으로, 4원을 가지고 4원을 만드는 경우의 수를 생각해보자. (4-4, 0원을 만드는 경우의 수)는 아무 동전도 추가하지 않은 공집합{ } 한 가지이다. 따라서 0원을 만드는 경우의 수에 4원 동전을 사용하는 케이스를 추가하면 {4원} 한 가지가 된다. 이를 dp[4]에 저장해주면 dp[4]는 2원으로 4원을 만드는 경우의 수 1가지, 4원으로 4원을 만드는 경우의 수 1가지가 더해져 총 2라는 값을 저장하게 된다. 

 

 

 

 위에 정리한 개념들을 가지고 코드를 읽어보면 이제 이해가 갈 것이다.

 

 

 

 

 

 

 

 

🙋‍♀️ 의견

 내가 싫어하는 DP 문제네......

 이번 문제 역시 가닥을 잘 못잡았는데, 아래 주소의 풀이가 많은 도움이 됐다.

 (https://ddb8036631.github.io/boj/9084_%EB%8F%99%EC%A0%84/)

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Main_백준_9084_동전_골드V {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		int TC= Integer.parseInt(br.readLine());
		
		for (int testCase = 1; testCase <= TC; testCase++) {
			int N = Integer.parseInt(br.readLine()); //동전의 가지 수
			int[] coins = new int[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				// 1~10000
				coins[i] = Integer.parseInt(st.nextToken());
			}
			int M = Integer.parseInt(br.readLine()); //만들어야 하는 금액
			//input
            
			// dp[m]: m원을 만들 수 있는 가지 수 
			int[] dp = new int[M+1]; //1~M
			dp[0] = 1;
			for (int i = 0; i < N; i++) {
				int coin = coins[i];
				for (int j = coin; j <= M; j++) {
					dp[j] += dp[j-coin];
				}
			}
			sb.append(dp[M]).append("\n");
		}//end of testCase
		System.out.println(sb);
	}//end of main
    
}//end of class

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨