서로 다른 값의 동전 k종류가 있고, 종류마다 얼마든지 쓸 수 있다.
동전 몇 개를 골라 합이 정확히 N원이 되게 하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력하라.
쓰는 동전의 종류별 개수가 같으면 같은 방법이다(순서는 따지지 않는다: 1+2와 2+1은 한 가지).
동전을 하나도 쓰지 않는 것도 방법이므로 N = 0이면 답은 1이다.
만들 수 없으면 0을 출력한다.
첫 줄에 N과 k, 둘째 줄에 동전 값 c₁ … c_k가 빈칸으로 나뉘어 주어진다.
5 3 1 2 5
4
3 1 2
0
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
ways[x] = 'x원을 만드는 방법 수'로 두고 ways[0] = 1(아무것도 안 씀)에서 시작해, 동전 c마다 x = c … N에 ways[x] += ways[x - c]를 해요.
k × N ≤ 100만 번이라 모든 언어가 빨라요.
함정 둘: 반복의 바깥이 동전, 안쪽이 금액이어야 순서를 따지지 않는 수가 돼요 — 바꾸면 1+2와 2+1을 따로 세요.
그리고 방법 수는 금세 10¹⁸을 훌쩍 넘으니 더할 때마다 % 1000000007를 해야 해요.
끝에서 한 번만 나누면 C·C++·Java·C#의 long은 넘쳐서 엉뚱한 값이 되고, JavaScript·TypeScript·크레이콘의 수(배정밀도)는 2^53을 넘으면서 정확하지 않게 돼요.
Python만 정수 크기에 끝이 없어서 답은 맞지만, 수백 자리 수를 더하느라 느려져요.
두 값이 모두 1,000,000,007보다 작으면 합은 약 20억이라 32비트 int(약 21억)에 겨우 들어가요 — 그래서 여기서는 int로 충분하지만, 곱하거나 셋 이상 더하면 long/long long이 필요해요.
나머지 연산은 모두 %예요(크레이콘도 %).
배열 만들기: Python [0] * (n + 1), JS new Array(n + 1).fill(0), C++ vector<int>(n + 1, 0), Java·C# new int[n + 1], C static int ways[10000], 크레이콘 새목록(n + 1, 0) — N이 9,999까지라 크레이콘 목록 한도(10,000개)에 맞아요.
MOD = 1_000_000_007 n, k = map(int, input().split())coins = list(map(int, input().split())) # ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다ways = [0] * (n + 1)ways[0] = 1for c in coins: for x in range(c, n + 1): ways[x] = (ways[x] + ways[x - c]) % MODprint(ways[n])const MOD = 1_000_000_007;const [n, k, ...coins] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다const ways = new Array(n + 1).fill(0);ways[0] = 1;for (const c of coins) { for (let x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD;}console.log(ways[n]);import { readFileSync } from "node:fs";const MOD = 1_000_000_007;const [n, k, ...coins]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다const ways: number[] = new Array(n + 1).fill(0);ways[0] = 1;for (const c of coins) { for (let x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD;}console.log(ways[n]);import java.util.Scanner; public class Main { static final int MOD = 1_000_000_007; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), k = sc.nextInt(); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 int[] ways = new int[n + 1]; ways[0] = 1; for (int i = 0; i < k; i++) { int c = sc.nextInt(); // 두 값이 모두 MOD보다 작아서 합은 약 20억 — int(약 21억) 안에 든다 for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } System.out.println(ways[n]); }}using System;using System.Linq; class Program{ const int MOD = 1_000_000_007; static void Main() { int n = int.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[0]); int[] coins = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 int[] ways = new int[n + 1]; ways[0] = 1; foreach (int c in coins) { for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } Console.WriteLine(ways[n]); }}#include <iostream>#include <vector> constexpr int MOD = 1'000'000'007; int main() { int n, k; std::cin >> n >> k; // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 std::vector<int> ways(n + 1, 0); ways[0] = 1; for (int i = 0; i < k; i++) { int c; std::cin >> c; for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } std::cout << ways[n] << '\n';}#include <stdio.h> #define MOD 1000000007#define MAXN 9999 int main(void) { static int ways[MAXN + 1]; int n, k; scanf("%d %d", &n, &k); /* ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 */ ways[0] = 1; for (int i = 0; i < k; i++) { int c; scanf("%d", &c); /* 두 값이 모두 MOD보다 작아서 합은 약 20억 — int(약 21억) 안에 든다 */ for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } printf("%d\n", ways[n]); return 0;}MOD = 1000000007;첫줄 = 콘솔.수들읽기();n = 첫줄[0];coins = 콘솔.수들읽기(); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다ways = 새목록(n + 1, 0);ways[0] = 1;각각 (c 에서 coins){ 반복 (x = c; x <= n; x++) { ways[x] = (ways[x] + ways[x - c]) % MOD; }}콘솔.쓰기(ways[n]);