[그리디] 만들 수 없는 금액
N 개의 동전을 가지고 있고, 화폐 단위는 1,000,000 이하의 자연수다. 이때 N 개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구해라. 예를 들어 N = 5이고 각 동전이 3원, 2원, 1원, 1원, 9원 이라면 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다. 또 다른 예로 N = 3이고 각 동전이 3원, 5원, 7원 이라면 답은 1원이다. 문제를 보고 처음든 생각은 이랬다. 가능한 모든 수를 Set으로 저장해놓고 1부터 1,000,000 까지 for문 돌려서 없는 숫자가 나오면 답인것으로. 그런데 모든 수를 구하기 위한 방식이 마땅치 않았다. 답 코드를 보면 먼저 정렬 한 후에, 구해야 되는 target 숫자를 차례차례 체크하는 방식으로 이루어져 있다. 예를 들어 data..
2021. 10. 3.
[그리디] 큰 수의 법칙
n 개의 다양한 수로 이뤄진 배열이 있다. 그 수들을 m 번 더해서 가장 크게 만들어야 한다. 단, 배열안의 특정 수가 k번 초과해서 더해질 수는 없다. 예를들어 n이 5인 [2,4,5,4,6] 배열로 m이 8, k가 3(8번 더하지만 특정 수가 3번 초과하면 안됌)인 상황에서 가장 큰 수를 만드려면 6+6+6+5+6+6+6+5=46 이 된다. 그리고 서로 다른 인덱스지만 숫자가 같은 경우는 서로 다른 것으로 간주한다. 예를들어 [3,4,3,4,3] 인 배열에 m이 7이고 k가 2이면 4+4+4+4+4+4+4 = 28이 된다. 결국 배열에서 필요한 숫자는 가장 큰 수와 그다음 큰수 두개 뿐이다. 그래서 먼저 배열을 정렬하는게 첫 이슈인데 책에서 정렬까지 직접 구현하진 않았고 라이브러리를 이용했다. # 큰..
2021. 9. 13.
