DATA101

문제 문제 원본: https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 접근법 본 문제를 한 줄로 요약하자면, N가지 종류의 동전을 조합해 화폐 가치가 K원을 만들 때 필요한 동전의 최소 개수를 구하는 문제입니다. 본 문제는 그리디 알고리즘의 기초 예제인 거스름돈 문제와 변수 이름이나 표현방식이 다를 뿐 풀이 방법은 매우 흡사합니다. 그래서 저는 다음과 같이 일부 변수명을 거스름돈 문제..

안녕하세요, 이번 포스팅에서는 지난 포스팅에서 다룬 그리디 알고리즘 연습문제의 소스코드를 공유합니다. heytech.tistory.com/44 [알고리즘] 그리디(Greedy) 알고리즘에 대해 알아보자! (연습문제 포함) 오늘은 알고리즘 스터디 첫 번째 포스팅으로서 그리디 알고리즘에 대해 알아보도록 하겠습니다. 그럼 바로 시작하죠! 1. 그리디 알고리즘이란? 그리디(Greedy)는 그림 1 에서 보실 수 있듯이 사전 heytech.tistory.com 1. 연습문제 그리디 알고리즘의 가장 대표적인 예시 문제는 거스름돈 계산 문제입니다. Q. 당신은 카페의 계산을 도와주는 직원이며 카운터에는 거스름돈으로 사용하는 화폐로서 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정한다. 손님에게 제..