POJ-3181 : Dollar Dayz

問題概要

[1..K](K<100)円の硬貨が十分たくさんある。このときN(<1000)円の支払い方は何通りあるか求める問題。

解法

個数制限なしナップサックと同様にやればよい。最大ケースでは64bitでも足りないので多倍長が必要。

acceptされたコード

import java.math.BigInteger;
import java.util.Scanner;

public class Main{

	void run(){
		Scanner in = new Scanner(System.in);
		int N = in.nextInt(), K = in.nextInt();
		BigInteger[] ways = new BigInteger[N + 1];
		for (int i = 0; i < ways.length; i++) {
			ways[i] = BigInteger.ZERO;
		}
		ways[0] = BigInteger.ONE;
		for (int p = 1; p <= K; ++p) {
			for (int money = p; money < ways.length; money++) {
				ways[money] = ways[money].add(ways[money - p]);
			}
		}
		System.out.println(ways[N]);
	}
	
	public static void main(String args[]){
		new Main().run();
	}
}