간단하게 생각하면

1 4 5 7 원이있을때 10원을 만드는 방법이라면. 7 + 1, 1, 1 총 4개로 최소인데
5 5 가 최소가 되서 2개가 됩니다.

DP나 stack을 이용해서 푸시는게 맞다고 생각합니다.

아 ᄏᄏᄏᄏᄏᄏᄏ 감사합니다.

제가 문제를 이제 읽어봤는데 일반적인 방법으론 안될거같네요.

dp나 stack을 쓰려면 저 큰돈을 가지고있는 bool type 배열이 필요한데.

최소 1000mb가 필요합니다. 10^9 / 10^6 .

그러면 이걸 따로 저장할 배열이 필요하게되네요. bool visit[~~~];

3원 과 1원이 있다고 치면.

3원 - > 3, 4, 1 원 -> 3 4 1 6 7 4 (3중복 처리)

이런느낌이야합니다. 그래서 이전에 숫자가 나왔는지를 체크하기위해서

메모리 때문에 않되니.. 체크 배열을 만들어놓고. 3 4 1 넣고 다음에 3 4 1 6 7 4 넣고 넣기전에 이 배열안에 있었니?

라고 찾아야할 듯합니다. 그런데 여기서 체크배열이 길어지면 찾는데 시간이 소요겠네요.. 그래서 저라면 hash 개념을 써서.

100이면

visit[2][1000] = { } 이런식에다가 2번쨰 10^2승이니 넣고 검사할듯합니다.

10 ^18승이니 [18][???] 만큼이네요..

풀어보진 않아서 잘 모르겠으나... 그냥 이론은 이런듯합니다...