JAVA 동전 바꿔주기 알고리즘 에서 도출 과정 수식 출력

JAVA 동전 바꿔주기 알고리즘 에서 도출 과정 수식 출력

QA

JAVA 동전 바꿔주기 알고리즘 에서 도출 과정 수식 출력

본문

명보네 동네 가게의 현금 출납기에는 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();

    }

}

이 질문에 댓글 쓰기 :

답변을 작성하시기 전에 로그인 해주세요.
전체 8
QA 내용 검색

회원로그인

(주)에스아이알소프트 / 대표:홍석명 / (06211) 서울특별시 강남구 역삼동 707-34 한신인터밸리24 서관 1404호 / E-Mail: admin@sir.kr
사업자등록번호: 217-81-36347 / 통신판매업신고번호:2014-서울강남-02098호 / 개인정보보호책임자:김민섭(minsup@sir.kr)
© SIRSOFT