BOJ 11047 동전 0

n종류의 동전을 최소(개수)로 이용해서 k원을 만들어야 하는데, 이 문제에서 주어지는 n종류의 동전은 1원부터 시작해서 Ai원은 Ai-1원의 배수인 경우가 주어진다.
즉, 주어지는 n종류의 동전은 오름차순으로 나열되어 있고, X원의 동전은 X원 이하의 모든 동전의 배수가 된다.
보통 동전 문제는 다이나믹 프로그래밍으로 푸는 걸로 알고 있는데, 이 문제의 경우 X원의 동전은 X원 이하의 모든 동전의 배수이므로 가능한 동전 주 무조건 가치가 큰 동전을 우선적으로 써야한다. 그리디 문제이다.
가치가 큰 동전부터 우선적으로 써야하는 것을 명확하게 증명은 못하겠지만, 생각해보면 배수가 아닌 경우에는 5원*3= 15원 , 12원*1+1원*3= 15원.. 이런 예에서 볼 수 있듯이, 가치가 큰 동전을 우선적으로 썼을 때, 더 개수가 많이 필요한 경우가 있다. 하지만 이렇게 배수들로 주어지는 경우에는 일단 같은 수를 여러번 쓸 바에야 그 배수를 쓰는 것이 훨씬 이익인데, 이 것만으로는 완벽히 증명이 힘들다.
  최소 배인 2배만 한다고 해도, 1원부터 시작할 경우 1, 2, 4, 8, 16, 32, 64, 128,... 어떤 수에 대해서 그 수의 앞의 수들을 다 합쳐서 어떤 수보다 작다. 만약 3배, 4배를 한다면 더 큰 차이가 날 것이다.
어떤 수에 대해서 그 수의 앞의 수들을 다 합쳐도 그 수보다 작기 때문에 가장 큰 수를 우선적으로 이용하는 것이 개수를 줄이는 데 좋을 것이다.

하지만... 그래도 완벽히는 증명은 못하겠다. 일단 직관적으로는 90퍼센트 확실한 것 같은데... 일단 풀어봐야 겠다. 나중에 더 공부하고 다시 생각해보자.