![]()
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 풀이과정 ①문제 바라보기 기본적인 그리디 문제다. 어렵게 낼 수 있다면 굉장히 어렵게 낼 수 있는 문제인데 이 문제의 경우에는 굉장히 기본기본기본적인 문제같다. ②아이디어 펼치기 연산자 %와 //을 활용하면 간단히 풀릴 것이다. 몫을 구해서 만약 1 이상이라면 남는 돈은 %한 값이 되는거고 빠져나간 동전의 개수는 //가 되는 것이다...
그리디 알고리즘이란, 단순하지만 강력한 문제 해결 방법이다. 이 유형은 "탐욕법"이라 소개되기도 하는데, 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 "탐욕적"이라는 말은 '현재 상황에서 지금 당장 가장 좋은 것만 고르는 방법"을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 출제 동향 이 유형은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 다익스트라 알고리즘과 같이 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기는 어렵다. 그리디 알고리즘 유형의 ..
