BaekJoon 11047 동전 0

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

소스결과 1984 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 그리디 알고리즘, 동전교환

 

설명

내가 가지고 있는 동전의 종류를 가지고 동전이 최소로 몇개만 있으면 되는지 푸는 문제

 

일상생활에서 내가 잔돈을 어찌 냈더라?

지폐를 안쓰고 내가 동전을 낸다면 어떤 순서로 낼지 생각해보자, 거스름돈이 없게 만들면서

 

알고리즘

1. 내가 낼 수 있는 가장 큰 동전부터 값이 넘치지 않게 최대 갯수로 낸다.

2. 내가 낸 동전의 값만큼 줄여 가면서 목표 값이 0이 될 때 까지 반복한다.

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int main()
{
	int timeTable[1000];
	int n;
	int sum = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
		scanf("%d", &timeTable[i]);

	// Selection Sort

	for (int i = 0; i < n; i++)
	{
		int min = i;
		for (int j = i; j < n; j++)
			if (timeTable[min] > timeTable[j])
				min = j;
		swap(timeTable[i], timeTable[min]);
	}
	
	for (int i = 1; i < n; i++)
		timeTable[i] += timeTable[i-1];

	for (int i = 0; i < n; i++)
		sum += timeTable[i];

	cout << sum;

	return 0;
}