[BOJ][Python]2720번 풀이

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

2720번: 세탁소 사장 동혁

t = int(input())
d = [25,10,5,1]
for _ in range(t):
    c = int(input())
    ans = []
    for i in d:
        ans.append(c//i)
        c %= i
    print(*ans)

solved.ac 사이트에서 개인 정보를 확인하면 어떤 알고리즘의 문제를 많이 풀었는지 그래프로 나타내주는 기능이 있는데요. 그리디를 하나도 안 푼 수준으로 안풀었더군요. 그래서 그런가 실버 상위권 그리디 문제가 나오면 자주 막히는 것 같아서 예전에 dp 때처럼 그리디 보충 수업을 진행하기로 했습니다. 한동안 그리디 문제 풀이가 자주 올라올 것 같네요.

 

그리디 알고리즘을 사용할 때 선행되어야 하는 조건에는 '앞의 선택이 이후에 영향을 주지 않는다' 와 '최종적인 답은 부분에 대한 최적의 해결 방법으로 구성된다' 라는 두 가지 조건이 꼭 성립되어야 한다고 합니다. 2번째 조건은 상당히 dp와 비슷하다는 느낌이 드는데요. 실제로 그리디는 dp를 사용할 때 불필요하게 많은 일을 하는 경우 이를 보완하기 위해 고안된 알고리즘이라고 하네요. 가끔 dp 문제를 풀다보면 브루트 포스나 그리디가 함께 쓰여있는 경우가 있는데 그래서 그런가 봅니다.

 

해당 문제는 그리디 문제의 대표적인 최소 동전 갯수 구하기 문제입니다. 처음이라고 대표적인게 맨 앞에 포진되어 있는 것 같네요. 해당 문제는 위에서 말했던 두 가지 조건을 만족한다고 볼 수 있습니다. 먼저 1센트 단위의 동전이 있다보니 끝까지 갔을 때 무조건 답이 나눠떨어지는 구조로 되어있기 때문에 앞에서 어떻게 선택을 하든 최종적인 해가 나온다는 특징으로 인해 앞에서의 선택이 이후에 영향을 주지 않죠(예전에 풀었던 배낭 문제 같은 경우 가치가 높은 것들만 선택해서 나아갔을 때 마지막에는 이미 집어넣은 걸 빼고 다른 걸 넣는 방법이 훨씬 높은 가치를 만들어 내는 등의 영향을 주었습니다). 또한 최종적인 답이 애초에 동전의 최소 갯수를 구하는 것이기 때문에 처음부터 높은 가치의 동전을 많이 쓰는게 최적의 해결 방법이 되는 구조를 가지고 있죠. 어떻게 보면 문제에서 하라는 대로 하는게 조건이 맞춰질 수 밖에 없는 구조를 가진 문제라고 볼 수 있겠습니다.

 

따라서 저는 큰 금액의 동전부터 사용할 수 있게 동전의 가치가 큰 순서대로 리스트를 만들었고 반복문을 통해서 몫을 답에 집어넣고 나머지로 c를 초기화해서 다음 반복문에서 차질없이 사용할 수 있도록 코드를 구성했습니다.