문제

BOJ 2293: 동전 1 https://www.acmicpc.net/problem/2293

풀이

조건

• n가지 종류의 동전으로 그 가치의 합이 k원이 되도록 한다.
• 그 경우의 수를 구한다.
• 각각의 동전은 몇 개라도 사용할 수 있다.

풀이 순서

• DP를 사용한다.
• 점화식은 DP[i] = DP[i] + DP[i - (동전 값)]
• 단순히 DP[i] = DP[i] + DP[i - (동전 값)] 만 해주면 중복된 값이 더해진다.
  • 예를 들어, 3을 구할 때 (1, 1, 1), (1, 2), (2, 1) 중 (1, 2), (2, 1)가 중복된다.
  • 이를 해결하기 위해 동전의 값을 인덱스로 하여 목표 값까지만 위의 점화식을 적용하면 중복을 제거한 결과가 저장된다.

코드

Java

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

public class Main {

	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[] dp = new int[k + 1];
		dp[0] = 1;
		
		
		int[] coins = new int[n + 1]; // 동전 종류 저장할 배열
		for (int i = 1; i <= n; i++) {
			// 동전 종류 저장
			coins[i] = Integer.parseInt(br.readLine());
			// 현재 동전 값부터 목표 값 까지만 -> 중복 제거 가능
			for (int j = coins[i]; j <= k; j++) {
				dp[j] += dp[j - coins[i]];
			}
		}

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

}

정리

• 중복을 제거할 수 있는 방법을 생각하지 못해 오래걸렸다.