11047번 동전0

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

11047번: 동전 0

동전 0 문제는 그리디 알고리즘을 이용한 문제입니다.

그리디 알고리즘이란?
간단히 말해서 하나의 트리에서 최종 출력값이 가장 큰 것이 아닌 지금 바라보고 있는 상태에서 가장 큰것을 가져가면서 트리를 타고 내려가게 되는 알고리즘입니다.

107이 결과적으로 더 크지만 그리디 알고리즘에 따라 13으로 넘어가고 11로 넘어가 출력은 24가 된다

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int n, nu, num[10];
	int temp = 0;

	scanf("%d %d", &n, &nu);

	for (int i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}
    
	for (int i = n-1; i >= 0; i--) {
		if (nu < num[i])
			continue;
		temp += nu / num[i];
		nu%=num[i];
	}
    
	printf("%d", temp);
}

 

이에 따라 이번 문제에서는 여려개의 값을 받아 반복하기 위해 배열을 써줍니다.

배열안에 동전들의 단위가 주어지고 다시 배열을 거꾸로 돌리면서 계산하고자 하는 값보다 단위값이 더 크면 무시하고 반복합니다.

반복하면서 만약 단위가 나누려는 값보다 작아지면 if 문에 의해 걸러지고 있던 반복문의 연산이 시작됩니다.

temp 에 값을 나눈값의 몫을 더 해주고 다시  nu (나눠야할 값)에는 아까의 수식에서의 나머지를 넣어줍니다. 이 것을 반복해서 결과가 출력이 됩니다.

좋네용

예를 들어서 입력값이 4200 원일땐 5000원까지는 4200 보다 크기 때문에 if 문에서 continue 가 되고 1000원이 됐을때 1000원으로 4200을 나눠줍니다. 몫을 저장하게되면 1000원 4개가 사용됐다고 표현할 수 있고 나머지 값 200원이 남게됩니다. 

다시 그럼 200원보다 작아질때까지 포문이 돌고 200원보다 작아지면 아까와 같이 200/100 의 몫 2가 들어가고 나머지가 없기 때문에 temp 에는 6개 라는 값이 들어가게 됩니다.