[BOJ] 11047 동전 0

Link

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

Note

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

일상생활에서 내가 잔돈을 어찌 냈더라?
지폐를 안쓰고 내가 동전을 낸다면 어떤 순서로 낼지 생각해보자, 거스름돈이 없게 만들면서

알고리즘

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;
}

2019-01-16 11:30:00에 Tistory에서 작성되었습니다.