[C++] 2720번 세탁소 사장 동혁

문제

 

코드

#include <iostream>
using namespace std;


int main()
{
	int n, j;
	int arr[4] = { 25, 10, 5, 1 };
	cin >> n;
	int a, b, c, d;
	
	for (int i = 0; i < n; i++)
	{
		cin >> j;

		a = j / arr[0];

		j -= a * arr[0];

		b = j / arr[1];

		j -= b * arr[1];

		c = j / arr[2];

		j -= c * arr[2];

		d = j / arr[3];

		j -= d * arr[3];

		cout << a << " " << b << " " << c << " " << d << endl;
	}
	return 0;
}

 

문제 해설

금액을 각각의 동전 단위로 나누어서 최소 동전을 환산하는 것입니다. 이같은 경우 탐욕적 알고리즘을 사용하면 금방 풀 수 있습니다. 

 

일단 저는 그냥 흐름대로 코딩을 작성하여서 제 코드가 최선의 알고리즘은 아닐겁니다.

 

int n, j;
int arr[4] = { 25, 10, 5, 1 };
cin >> n;
int a, b, c, d;

입력 및 변수 초기

 

n은 테스트 케이스의 개수를 저장합니다. 이후 j는 각 테스트 케이스에서 주어진 금액을 저장하고 arr은 동전 단위를 저장한 배열입니다 (쿼터는 25센트, 다임은 10센트, 니켈은 5센트, 페니는 1센트)

 

a, b, c, d는 각각의 동전의 개수를 저장할 변수입니다. 

 

for (int i = 0; i < n; i++)
{
    cin >> j;

forr문을 통해 처음 입력받은 개수만큼 반복을 해줍니다.

 

a = j / arr[0];
j -= a * arr[0];
  
b = j / arr[1];
j -= b * arr[1];

c = j / arr[2];
j -= c * arr[2];

d = j / arr[3];
j -= d * arr[3];

동전을 단위별로 나눕니다.

 

a는 j에서 쿼터 동전의 개수를 구한 후 구한 쿼터 동전의 총액은 j에서 빼주는 형식으로 d까지 진행이 됩니다.

 

이후에 각각 a, b, c, d를 개수를 출력하면 코드는 마무리가 됩니다. 

 

아마 다른 사람들의 풀이도 이런 기본적인 방법은 같을 거라고 생각이 듭니다. 아니면 while문을 통해 if(total>=25) 이런 식으로 해주어도 되며 

 

int main() {
    cin >> T;

    while(T--) {
        int Q=0,D=0,N=0,P=0;
        cin >> paymoney;
        while(paymoney) {
            if(paymoney>=25) {
                Q++;
                paymoney-=25;
            } else if(paymoney>=10) {
                D++;
                paymoney-=10;
            } else if(paymoney>=5) {
                N++;
                paymoney-=5;
            } else {
                P++;
                paymoney-=1;
            }
        }
        cout << Q <<" "<< D <<" "<< N <<" "<< P << "\n";
    }
}
출처: https://tooo1.tistory.com/258 [개발자 퉁이리:티스토리]

다른 사람의 풀이처럼 이런 식으로 해주어도 올바른 풀이가 됩니다.