[이것이 코딩테스트다 그리디(탐욕법)] 예제 3-1 거스름돈 with Python, C++

[문제]

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재, 손님에게 거스러 줘야 할 돈이 N원일 때 거스러줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

[풀이]

이 문제의 핵심은 탐욕법 사고로 접근하는 것이다.

탐욕법은 "현재 상황에서 지금 당장 좋은 것만 고르는 방법" 인데

가장 최소를 구할려면 가장 큰 거스름돈 부터 거슬러 주면 된다.

즉, 가장 큰 화폐 단위부터 거슬러 주면서 카운트 하면 된다.

 

with Python

 

-- 추후 업데이트

 

 

with C++

int main(){
	int n = 1260;
	int coin_type[4] = {500, 100, 50, 10}; 
	int answer = 0;
	
	for(int i=0; i<sizeof(coin_type)/sizeof(int); i++){
		answer += (n / coin_type[i]);
		n = n % coin_type[i];
	}
	return answer;
}

 

참고로 위의 문제는 이것이 취업을 위한 코딩 테스트다 with 파이썬 책에 나온 문제입니다.

책 정보는 아래와 같습니다.

 

www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬

오늘부터 이 책으로 열심히 코테를 준비해볼란다!!