2293 동전 1

n개의 동전을 조합하여 k원을 만들 때 만들 수 있는 모든 경우의 수를 구하는 문제이다.
이 문제는 TLE가 중요하게 작용한다.
내가 처음에 생각한 방법은 재귀로,각 동전으로 만들 수 있는 돈의 모든 경우로 분기하여
K원이 될때 표시해주는 방식이었는데, 답은 정확했으나 쉽게 TLE가 발생했다.

그 다음으로 생각한것이 dp인데, 동전으로 만든 각 원에 대한 index 배열을 생성하고,
해당 동전을 0개~m개 사용할 때의 경우를 가정하여 계산했다.
정답은 맞았으나 다른 사람의 소스에 비해 시간이 많이 느렸다.

그래서 다른 사람의 소스를 살펴본 결과,
각 동전의 값어치 부터 k원까지 증가시키면서, 그 값에 원래의 값어치를 감소 시켰을 때의 배열값을 덧붙여 나가는 방법으로 해서, 소스도 시간도 줄이는 멋진 코드가 되었다.

역시 다른사람들의 소스를 보는것은 중요한 것 같다.

소스