동전 1

문제

언어

  • Java
  • 본 문제의 경우, JavaScript 로 풀면 메모리 초과가 발생해서 부득이하게 Java 로 포스트하게 되었습니다.

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기

문제 풀이 step 1

  • dp[k][n] = n 개의 동전으로 k 원을 만들 수 있는 경우의 수
    • 예를들어, dp[10][1] 은 1 개의 동전으로 10 원을 만들 수 있는 경우의 수입니다.
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 문제의 예시를 이용해서 정의한 dp 를 풀어보자면,
    • k = 10, n = 1 이면, 1 원 동전으로 10 원을 만들 수 있는 경우의 수입니다.
    • k = 10, n = 2 이면, 1 원 동전과 2 원 동전으로 10 원을 만들 수 있는 경우의 수입니다.
    • k = 10, n = 3 이면, 1 원 동전과 2 원 동전과 5 원 동전으로 10 원을 만들 수 있는 경우의 수입니다.
    • dp[9][n] 까지 다 채워져있다고 가정하고, dp[10][n] 을 채울 떄,
      • dp[10][1] 은 “1 원 동전 -> 10 원” 인 경우로 dp[9][1] 의 각 경우의 수에 1 원 씩 더한 것과 같습니다.
      • dp[10][2] 는 “1 원, 2 원 동전 -> 10 원” 인 경우로 dp[10][1] 과 dp[8][2] 의 각 경우의 수에 2 원씩 더한 것과 같습니다.
      • dp[10][3] 은 “1 원, 2 원, 5 원 동전 -> 10 원” 인 경우로 dp[10][2] 와 dp[5][3] 의 각 경우의 수에 5 원씩 더한 것과 같습니다.
    • 이를 일반화하면 dp[k][n] = dp[k][n - 1] + dp[k - coin[n]][n] 과 같은 점화식을 구할 수 있습니다.
  • 점화식을 이용해서 “Bottom Up” 방식으로 밑에서부터 하나하나씩 다 채운 후에 dp[k][n] 을 출력하면 정답이 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 다시 풀면서 느낀 것은 “사용한 동전의 구성이 같은데 순서만 다른 것은 같은 경우”라면 동전을 오름차순으로 정렬해서 풀면 된다는 것이었습니다.
  • 왜냐하면, 오름차순으로 정렬하게 되면, 각각의 경우의 수를 구별할 수 있게 되기 때문입니다. (정렬을 통해 순서를 부여하는 방식)

소스 코드

import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		int[] coin = new int[n + 1];
		// 편의를 위해 동전의 종류가 0 개인 경우를 정의합니다.
		coin[0] = 0;
		for(int i = 1; i < n + 1; i++) {
			coin[i] = sc.nextInt();
		}

		int[][] dp = new int[k + 1][n + 1];

		// base
		// base 는 동전의 종류가 0 개인 경우만 0 으로 하고, 나머지는 1 로 초기화합니다.
		for(int i = 1; i < n + 1; i++) {
			dp[0][i] = 1;
		}

		for(int i = 1; i < k + 1; i++) {
			for(int j = 1; j < n + 1; j++) {
				// 사용하려는 동전이 만드려는 금액보다 큰 경우
				if(i - coin[j] < 0) dp[i][j] = dp[i][j - 1];
				// 점화식에 따라서 dp 배열 채우기
				else dp[i][j] = dp[i][j - 1] + dp[i - coin[j]][j];
			}
		}

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