[Java] DP - 응용

1. 이항 계수 구하기

 

가. 이항 계수

 

• 이항 정리
  : 이항식의 거듭제곱을 이항 계수를 계수로 하는 일련의 단항식들의 합으로 전개하는 정리.
• 이항 계수
  : 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

 

(x+y)^3 = x^3 + 3x^2y + 3xy^3 + y^3

 

조합으로 이항 계수를 구할 수 있다.

 

 

위와 같이 일반화할 수 있다.

 

---

나. 조합 공식

 

nCr = n! / (r!( n-r)!)

조합 공식 - 계산량이 많은 팩토리얼(n!, r!)을 계산하지 않고 아래의 수식을 이용한다.

 

nCr = (n-1)C(r-1) + (n-1)Cr

이는 재귀 함수로 구현할 수 있다.

 

comb(n, r)
    IF n==k or k==0 : RETURN 1 // 모두 뽑거나 하나도 안 뽑는 경우
    ELSE : RETURN comb(n-1, r-1) + comb(n-1, r)

중복되는 계산을 줄이기 위해서 메모이제이션을 활용한다.

 

순수 함수, 중복 부분문제 구조, 최적 부분문제 구조를 만족하기 때문에 DP로 구현할 수 있다.

 

---

다. 파스칼의 삼각형

 

• 이항 계수를 삼각형 모양으로 나열한 것.

 

무려 13살의 파스칼 선생님이 이항 계수를 구하기 위해서 사용하셨다… ㄷㄷㄷ

 

이항 계수를 구할 때 뿐만 아니라 조합을 DP로 표현할 때도 사용된다.

 

// 파스칼 삼각형을 이용한 이항계수 계산
import java.util.Arrays;
import java.util.Scanner;

public class BinomialCoefficientTest {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        //int[][] B = new int[N+1][N+1];
        int[][] B = new int[N+1][K+1]; // 0C0 ~ nCk. K+1 : 불필요한 연산 생략

        for(int i=0; i<=N; i++) {
            for(int j=0, end=Math.min(i,  K); j<=end; ++j) { // 
                if(j==0 || j==i) B[i][j] =1;
                else B[i][j] = B[i-1][j-1] + B[i-1][j];
            }
        }

        for(int[] arr : B) {
            System.out.println(Arrays.toString(arr));
        }

        System.out.println(B[N][K]);
        sc.close();
    }

}

/*
4 2
[1, 0, 0]
[1, 1, 0]
[1, 2, 1]
[1, 3, 3]
[1, 4, 6]
6
*/

• int[][] B = new int[N+1][K+1]; , for(int j=0, end=Math.min(i, K); j<=end; ++j) { : 불필요한 계산은 생략

 

for(int i=0; i<=N; i++) {
    for(int j=0, end=Math.min(i,  K); j<=end; ++j) {
        if(j==0 || j==i) B[i][j] =1;
        else B[i][j] = B[i-1][j-1] + B[i-1][j];
    }
}

• nCk = (n-1)C(k-1) + (n-1)Ck를 DP로 구현.

 

• for(int j=0, end=Math.min(i, K); j<=end; ++j) {
  : end=Math.min(i, K)가 없으면 i가 int[N+1][K+1]의 K를 넘어서면서 ArrayIndexOutOfBoundsException을 발생한다.

 

---

2. 거스름돈 구하기

 

1원, 4원, 6원짜리 동전이 있다고 하자.

 

8원을 거슬러주어야 하면 최소 몇 개의 동전을 거슬러 주어야 하는가?

import java.util.Arrays;
import java.util.Scanner;

public class MinCoinTest {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D = new int[N+1]; // 각 금액을 만드는 최소 동전수 (최적해)

        D[0] = 0;
        for(int i=1; i<=N; i++) { // i : 금액
            int min = D[i-1] + 1; // 1원을 사용했을 경우로 초기화
            if(i>=4) min = Math.min(min, D[i-4] + 1);
            if(i>=6) min = Math.min(min, D[i-6] + 1);

            D[i] = min;
        }

        System.out.println(Arrays.toString(D));
        System.out.println(D[N]);
        sc.close();
    }

}

/*
8
[0, 1, 2, 3, 1, 2, 1, 2, 2]
2
*/

• for(int i=1; i<=N; i++) { : 적은 금액부터 목표 금액 N까지 상향식으로 접근.
• int min = D[i-1] + 1; : 1원을 사용했을 경우로 초기화.
• if(i>=4) min = Math.min(min, D[i-4] + 1); : 4원을 거슬러 줄 때.
• if(i>=6) min = Math.min(min, D[i-6] + 1); : 6원을 거슬러 줄 때.

 

---