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(); } }