[BOJ] 1943번: 동전 분배

https://www.acmicpc.net/problem/1943

기본적인 아이디어는 Dynamic Programming입니다. 예를 들어 1원짜리가 100개 있을 경우, D[i] = true일 경우 D[i+1], D[i+2], ... , D[i+100]를 true로 만드는 것입니다. 이 때 i는 내림차순으로 살펴봐야합니다.(그렇지 않으면 1원짜리가 100개 있는데도 D[0]부터 D[50000]까지 전부 true로 판단해버릴 수 있기 때문입니다.)

그런데 잘 생각해보면 1원짜리가 100000개 있을 경우 이 방식대로 정직하게 수행하면 100000*100000/2번의 연산이 필요해 시간초과가 발생합니다. 이렇게 발생할 수 있는 시간초과를 회피하기 위해 다양한 방법으로 시간을 커팅했고, 그 결과 96ms에 Accepted를 받을 수 있었습니다.

다른 정답자들의 코드를 보니 재귀적으로 풀어낸 코드도 몇개 발견을 했는데 코드를 잘 이해하지 못했습니다.

https://github.com/blisstoner/BOJ/blob/master/1943.cpp