백준 11047 동전0 [c++]

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;	//동전의 종류 n, 가치의합 k

	cin >> n >> k;
	int* arr = new int[n];	//동전의 종류를 저장할 배열
	int result = 0;	//결과를 저장할 변수

	for (int i = 0; i < n; i++)	//동전의 종류 입력하는 반복문
	{
		cin >> arr[i];
	}

	for (int i = n - 1; i >= 0; i--)	//동전은 오름차순으로 주어짐으로 높은동전부터 적용하는 반복문
	{
		if (k % arr[i] != k)	//k를 동전으로 나눴을때 나머지가 k가 아닌경우 (나눠질경우)
		{
			result += k / arr[i];	//결과값에 나눈 후의 몫을 더한다.
			if (k % arr[i] == 0)	//나머지가 0 이라면 반복문 종료
				break;

			k = k % arr[i];	//나머지가 0이 아닐경우에 k의 값에 나눈 후 나머지를 저장
		}
	}

	cout << result;	//결과출력

	
	return 0;
}