[백준 2720] 세탁소 사장 동혁

문제

www.acmicpc.net/problem/2720

 

알고리즘

구현

 

풀이

이 문제는 제가 파이썬 구현 연습을 위해 풀다가 마주한 문제입니다. 구현 외에 짚고 넘어갈 점이 있어 포스팅하겠습니다.

 

저는 브론즈3이라는 점에서 구현 외에 별 다른 부분은 신경쓰지 않고 풀었던 문제입니다. 하지만 조금 생각해본다면 수상한 점을 발견할 수 있습니다.

 

문제 내용은 거슬러 주는 동전의 갯수를 최소화 하는 문제입니다. 그리디 또는 다이나믹 프로그래밍을 다룰 때 많이 등장하는 주제중 하나입니다. 그리디로 문제를 해결하려고 동전의 값을 보았지만 거슬러 줄 수 있는 동전의 값은 25원 10원 5원 1원 입니다. 동전들 끼리 배수관계를 만족하지 못하므로 (25원과 10원) 다이나믹 프로그래밍을 이용해 해결하자!

라고 생각할 수 있습니다.

 

하지만 이 문제는 그리디로 해결 가능합니다. 25보다 큰 10의 배수인 30은 25+5 동전을 사용하는 것이 10+10+10보다 이득이므로 그렇습니다. 일반적으로 설명하자면 (25,10,5,1)은 canonical을 만족하기 때문입니다.

 

동전끼리 배수관계를 만족할 때는 무조건 canonical을 만족하고, 배수가 아니더라도 canonical을 만족하는 coin들이 있기 때문입니다. 이와 관련된 문제는 여기와 여기서 만날 수 있습니다.