PS
BOJ 11047 동전 0
boj 11047 동전 0 그리디 알고리즘을 활용하여 풀 수 있는 문제여서 적용하여 풀어보았다. DP를 활용한 풀이도 생각할 수 있는 문제이지만, DP를 활용할 경우 O(NK)의 시간복잡도로 시간초과가 나와 그리디를 활용해야만 하는 문제였다. 그리디 알고리즘 문제의 풀이 흐름에 따라 풀어보았다. 직관적으로 높은 금액의 동전을 최대한 많이 사용할 수록 동전 갯수가 적어질 거라고 생각했다. 위 생각을 증명해보았다. 간단하게 하기 위해 동전의 가치가 10, 50, 100, 500원 뿐이라고 한다. '동전을 최소로 소모하여 값을 지불하기 위해서는 500원은 최대한, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 증명해보자. 증명을 편히 하기 위해 먼저 '..