그리디로 풀 수 있습니다

1. 구매한 숫자의 개수는 많을수록 좋습니다

2. 숫자의 총 개수가 같다면, 9를 많이 살수록 좋습니다

3. 총 개수랑 9의 개수도 같다면 8을 많이 살수록 좋습니다.

이렇게 숫자를 구매한 뒤, 내림차순으로 출력하면 됩니다

@palilo

답변 정말 감사합니다.

주신 조언대로 해볼려고 하였으나 시간복잡도에서 어떻게 해결해야 될지 모르겠어서요.

1.구매한 숫자의 개수는 많을 수록 좋습니다.

->이걸 구하긴 위해서는 가능한 모든 경우의 수를 전부 구해봐야 되는 것이 아닌가요?

즉,현재 남아있는 돈(cash)-(n-1)부터 0 원의 동전이 사용될때 들어가는 돈(coin[i]) >=0 일때 탐색을 하는 방법(재귀) 밖에 떠오르지가 않습니다.

이 부분을 어떻게 해결 해야 되나요?

제가 푼 방법을 그대로 설명드리자면,

1 ~ N까지의 숫자 중 가장 싼 숫자를 a라고 하겠습니다.

0 ~ N까지의 숫자 중 가장 싼 숫자를 b라고 하겠습니다. (b==0 또는 b==a입니다.)

가지고 있는 돈으로 a를 하나 사고 (만약 a 하나도 못 산다면 답은 0입니다.)

나머지 돈으로 b를 전부 삽니다.

이게 최대한 많은 숫자를 구입하는 방법입니다. (0만 아무리 많이 사도 0이니 0이 아닌 수 a는 최소한 한 개는 사야함)

이제 위에 산 숫자로 abb...bb 란 수를 만들었고, a와 b를 사고 남은 돈이 있을겁니다.

가장 앞 자리수를 N으로 바꿀 수 있다면 (남은 돈 >= N가격 - a가격) 앞 자리 수를 N으로 바꿉니다. 

N으로 바꿀 돈이 없다면 N-1로 바꿀 수 있는지 봅니다.

부족하다면 N-2 로 바꿀 수 있는지 봅니다...

이런식으로 가장 앞 자리수를 a이상의 수로 바꿀 수 있다면, 가장 큰 수로 바꿉니다.

두 번째 자리수인 b도 마찬가지로 반복합니다.

남은 돈이 다 떨어지거나 숫자의 끝에 도달할 때까지 반복하면 됩니다.

@palilo

흐아 ㅠㅠㅠ 맞았습니다.palilo 님 진심으로 감사드리네요 ㅠㅠㅠ

근데 이 문제가 실버1 의 난이도 인가요???

또한 왜 다이나믹 프로그래밍의 카테고리에 있는지 궁금하네요,,,,

+ palilo님 코드 정말 깔끔하시네요,,,코드 보면서 많이 배워가겠습니다