(중석유10)문제L: 중국몽(dp입문, 물문제)

화폐 교환 문제의 작은 변형
방금 dp를 정리했는데 마침 화폐 교환 변형 문제를 해냈어요. 사실 전에 한 글에서 제가 해결 방법을 말했는데 dp수문제로 할게요.
질문 L: 중국의 꿈
제목은 Z군이 방을 정리한 지 얼마 되지 않아 간단하게 세수를 하고 잠자리에 들었다고 한다. 중학교 3학년에 들어간 후 Z군은 꿈을 꾸지 않은 지 오래다. 꿈을 꾸지 않는 주요 원인은 학습 강도가 너무 높고 늦게 자서 잠만 자면 꿈도 꾸지 못할 정도로 깊이 잠들기 때문이다.오늘 밤 작은 Z의 뇌피부는 특히 흥분했다. 아마도 낮에 CZ중학교에서 수업이 너무 재미있었기 때문일 것이다. 이 Z는 잠이 들자마자 꿈나라로 들어갔다.꿈에서 Z는 조국을 대표하여 B국을 방문하여 국제정보학올림픽경기(International Olympiad in Informatics, IOI)에 참가하여 금메달을 딴 꿈을 꾸었다. 시상회가 끝난 후 Z는 근처 슈퍼마켓에 가서 선물을 사서 반 친구들에게 가져다 주었다. Z는 B국의 초콜릿이 사랑의 소망, 대중의 미련을 대표하고 음식 속의 왕이라고 생각했다.일찍이 19세기에 이미 세상에 유명해졌으니, 친구들에게 초콜릿 한 박스씩 사주면 틀림없이 큰 인기를 끌 것이다.그래서 샤오즈는 슈퍼마켓에 들어가자마자 초콜릿이 담긴 진열장으로 달려가 단숨에 고디바 초콜릿 40박스를 들고 계산대에 가서 줄을 서서 계산을 한다. 샤오즈가 계산할 차례가 되자 그는 자신이 가지고 있는 액면가가 큰 B국 지폐 한 장밖에 없다는 것을 발견했다. 그래서 그는 이 지폐를 건네주었다. 계산원은 신속하게 계산기에서 샤오즈에게 줄 금액을 계산한 다음에 돈궤를 열어 돈을 찾으려고 한다.작은 Z는 돈궤에 있는 동전이 액면가에 따라 큰 것부터 작은 것까지 가지런히 놓여 있는 것을 보고 일종의 액면가의 동전이 일렬로 늘어서 있는 것을 보았다. 이 광경을 보고 Z가 갑자기 영감을 얻었다. 소년궁이 이번 행사를 위해 시험문제를 모집하고 있는 것 같아서 이 제로 문제를 가지고 어린이들을 시험해 보는 것이 좋지 않겠는가?샤오즈는 호텔로 돌아오자마자 노트를 열고 명제를 시작한다. 수납원이 샤오즈에게 줄 금액 N, 금고 안의 동전 종류 K와 K종의 동전의 액면가를 계산하면 몇 가지 다른 거스름돈이 있는지 계산할 수 있다.이곳의'다름'은 거스름돈이 적어도 한 종류의 동전의 수량이 같지 않다는 것을 가리킨다.현재 동전 2종류만 있다고 가정하면 한 면액은 5점, 다른 한 면액은 1점, 작은 Z에게 줄 금액은 8점이며, 5점짜리 동전 1개에 1점짜리 동전 3개를 더하거나 8점짜리 동전을 찾을 수 있다.1점짜리 동전 3개에 5점짜리 동전 1개를 더하는 것은 본질적으로 1점짜리 동전 1개에 1점짜리 동전 3개를 더하는 것과 아무런 차이가 없기 때문에 두 가지 다른 방식으로만 8점을 찾을 수 있다.입력 데이터 첫 줄에는 두 개의 공백으로 구분된 정수 N과 K가 있는데 그 중 1≤N≤300은 슈퍼마켓 수납원이 작은 Z에게 줄 금액을 표시하고 1≤K≤8은 수납원의 금고에 모두 K종의 서로 다른 액면가의 동전이 있음을 나타낸다.2행에서 K+1행에는 1≤Ci ≤100의 양의 정수 Ci가 포함되어 있으며 이는 동전의 액면가를 의미하며 입력한 데이터에서 동전의 액면가를 내림차순으로 배열한다(최대에서 최소까지).종류에 따라 동전의 액면가가 각각 다르기 때문에, 종류마다 모두 무궁무진하게 취한다.출력 출력 데이터는 한 줄에 하나의 정수만 포함하여 슈퍼마켓 수납원이 가능한 제로 방안을 나타낸다.답안은 장정형 범위를 넘지 않을 것을 보증한다.주의해야 할 것은 액면가 1점짜리 동전이 없으면 일부 금액은 0을 찾을 수 없으며, 이때 결과는 0을 출력한다.샘플 입력 Copy 835 50 25 10 5 1 샘플 출력 Copy 159 힌트 샘플 설명 입력 설명
출력 상세 정보: 다음은 전체 159가지 찾기 시나리오 중 처음 15가지와 마지막 것입니다.
0×50 0×25 0×10 0×5 83×1 0×50 0×25 0×10 1×5 78×1 0×50 0×25 0×10 2×5 73×1 0×50 0×25 0×10 3×5 68×1 0×50 0×25 0×10 4×5 63×1 0×50 0×25 0×10 5×5 58×1 0×50 0×25 0×10 6×5 53×1 0×50 0×25 0×10 7×5 48×1 0×50 0×25 0×10 8×5 43×1 0×50 0×25 0×10 9×5 38×1 0×50 0×25 0×10 10×5 33×1 0×50 0×25 0×10 11×5 28×1 0×50 0×25 0×10 12×5 23×1 0×50 0×25 0×10 13×5 18×1 0×50 0×25 0×10 14×5 13×1 …………………………………………… 1×50 1×25 0×10 1×5 3×1
데이터 범위
10% 데이터 충족: N≤50, K≤3, Ci ≤10
30% 데이터 충족: N≤100, K≤5, Ci≤20
60% 데이터 충족: N ≤ 100, K ≤ 7, Ci ≤ 50
100% 데이터 충족: N≤300, K≤8, Ci≤100
**

다음 본문

**제목이 너무 길어서 줄일게요.1. 무한 개의 K종 화폐가 있는데 각각 가치 a[1], a[2],......a[k](한 수조에 넣는다).2、이것으로 N원으로 바꾸세요.3、몇 가지 환법이 있습니까?
데이터가 매우 커서, 분명히 깊이 검색할 시간이 초과되어, 너에게 dp를 하라고 강요한다.
코드를 직접 올리다.

#include 
using namespace std;
typedef long long LL;
const int inf = (int) 1e9+7;
const int MAXN = 32767+10;	//    N<32767 
LL dp[MAXN];
int main(){
     
    int n,k;
    cin>>n>>k;
    int a[k];
    for(int i=0;i<k;i++)	cin>>a[i];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for( int i=0; i<k; i++ ){
     
        for( int j=a[i]; j<=n; j++ )
            dp[j] = dp[j] + dp[j-a[i]];
    }
    cout<<dp[n]<<endl;
    return 0;
}

여기에서 내가 이전 문장의 화폐 교환 문제 코드를 복사한 것을 분명히 볼 수 있다.그리고 세부 사항을 고쳐서 앞의 문장을 비교하고 스스로 다른 것을 찾아라.
개인은 화폐 교환 문제를 보면 01배낭이 현저히 불합리하고 화폐는 무한개라고 생각한다. 디버깅 과정에서 점증식은 이것과 아무런 관계가 없다. 그리고 01배낭은 상태 이동 공식이라는 개념이 없다. 하나의 본질은 깊이 검색하는 것이고 하나는 dp이다.오류를 바로잡고 배낭9강을 본 후, 이런 문제는 01배낭문제는 아니지만, 완전배낭문제에 속한다(여기서 자세히 설명하지 않는다)