(2720) 세탁소 사장 동혁

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

단계별로 풀어보기

8단계(수학 1) 3번째

 

 

 

어떤 동전 단위의 배수가 다음 동전 단위라면 다음 동전 단위를 많이 쓰는 게 유리하다.

하지만 25센트는 10센트의 배수가 아닌데도 이런 그리디 풀이가 성립할까?

간단하게 말하자면 25센트 없이 만들 수 있는 최적 금액의 최댓값이 24센트로 25센트보다 작기 때문에 가능하다.

이런 계산 없이 그냥 그리디로 풀어도 되는 문제지만(예전에도 그렇게 풀었고) 깊게 파고들면 보기보다 어려운 문제였다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    int c;
    
    cin >> c;
    
    cout << c/25 << " ";
    c%= 25;
    cout << c/10 << " ";
    c%= 10;
    cout << c/5 << " ";
    c%= 5;
    cout << c << "\n";
  }
  
  return 0;
}