[백준 2293] 동전 1

https://www.acmicpc.net/problem/2293 문제이해 n가지 종류의 동전을 활용해 주어지는 k를 완성하면 된다. 동전의 개수는 무제한이고 사용한 동전의 구성은 같고 순서만 다른 경우는 같은 경우이다.

풀이 처음에는 dfs로 접근해서 모든 경우의 수를 구하니 사용한 동전의 구성은 같고 순서가 다른 경우를 모두 계산이 되었다. 그 후에 리스트를 만들어 리스트 내에 포함된 각 숫자의 개수를 구해 중복 여부를 확인하려니 더욱 간단한 방법으로 해결이 될 것 같아 고민을 했다. 3 10 1 2 5 위에 케이스에 대해서 직접 정답을 구해보니 1111111111 111111112 11111122 111115 1111222 11125 112222 1225 22222 55 다음과 같은 10개의 케이스가 존재했고 여기서 각 수는 오름차순으로 배열되어 있다.

그래서 dfs에 매개변수로 ex를 주어 이전에 더해진 숫자 이상으로만 더해질 수 있도록 조건을 주었다. 예제에 대한 출력은 잘...