레이팅 미적용명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 \(n_{1}\), \(n_{2}\), … , \(n_{k}\)개 씩 들어있다. 가게 주인은 명보에게 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, 각 동전 하나의 금액 \(p_{i}\)와 개수 \(n_{i}\)가 주어질 때 \((i=1,\) 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 \(2^{31}\)-1을 초과 하지 않는 것으로 가정한다.
※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.
첫째 줄에는 지폐의 금액 T(0＜\(T \le 10{,}000),\) 둘째 줄에는 동전의 가지 수 k(0＜\(k \le 100),\) 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 \(p_{i}\)(0＜\(p_{i} \le T)\)와 개수 \(n_{i}\)(0＜\(n_{i} \le 1{,}000)\)가 주어진다. \(p_{i}\)와 \(n_{i}\)사이에는 빈칸이 하나씩 있다.
첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.
20
3
5 3
10 2
1 5
4
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2002 > 2차 대회 > 중등부 2번