명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

20 = 10×2

20 = 10×1 + 5×2

20 = 10×1 + 5×1 + 1×5

20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법 의 수는 231을 초과하지 않는 것으로 가정한다.

참고 소스로 위와 같이 조건을 입력했을 때 "4"가 나옵니다.
그런데 위 4가지 경우의 수 수식도 함께 나오게 하려고 합니다.
어떻게 하면 될까요?

 

[참고소스]

import java.util.Scanner;

public class Main {

    static int T; // 지폐의 금액

    static int K; // 동전의 가지수

    static int [] Pi; // 각 동전의 금액

    static int [] Ni; // 각 동전의 개수

    static int [][] D; // 다이나믹 배열

      

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

          

        T = sc.nextInt();

        K = sc.nextInt();

          

        D = new int [K+1][T+1];

        Pi = new int[K+1];

        Ni = new int[K+1];

          

        D[0][0] = 1;

          

        for(int i=1; i<=K; i++) {

            D[i][0] = 1; // j위치에서 현재동전금액을 뺀곳의 값을 참조함

              

            Pi[i] = sc.nextInt();

            Ni[i] = sc.nextInt();

        }

          

        for(int i=1; i<=K; i++) {

            for(int j=1; j<=T; j++) {

                // 이전 동전이 만든 잔돈과

                // 내가 만들 잔돈을 더해 주면

                // 잔돈을 만들수 있는 케이스가 합쳐진다.

                for(int k=0; k<=Ni[i]; k++) {

                    if(Pi[i]*k > j) break;

                    D[i][j] += D[i-1][j-Pi[i]*k];

                }

            }

        }

        System.out.println(D[K][T]);

        sc.close();

    }

}