음악가의 알고리즘 공부

거스름돈을 큰 수부터 차례대로 나누어 몫은 결과값에 더해주고 나머지는 다음 크기의 동전으로 나누어주면 된다.

모든 로프를 사용해야 할 필요가 없다는 부분만 인지하면 크게 어려울 것은 없을 듯 하다.

한참을 고민해봐도 방법이 떠오르지 않아 결국 구글링을 통해 다른 분들의 방법을 확인하여 풀었다. 핵심은 각 자리수의 합이 3의 배수이며 0을 포함하고 있을 때 큰 수부터 배치하면 된다는 것. 가방끈이 짧아서 그런지 항상 이렇게 기초적인 수학을 이용하여 풀어야 하는 문제

최대한 많은 수로 이루어져야 하므로, 1부터 차례대로 더한 합을 입력받은 값과 비교하면 되는 문제다. 입력받는 s의 크기가 정수형의 범위를 한참 벗어나므로 long으로 선언해주어야 한다.

입력받은 수를 하나씩 나누어 배열에 저장하고 내림차순 정렬 후 출력해주면 된다.

Comparator를 이용해 정렬하면 쉽게 풀 수 있다.Comparator를 상속받아 직접 수식을 세우는 과정이 아직 익숙하지 않아 더 연습이 필요할 듯 하다.

Dual-Pivot Quick Sort를 이용하는 Arrays.sort를 사용해도 아슬아슬하게 정답인정은 되긴 하나, 입력 가능한 수의 최대 갯수가 입력받는 수의 범위보다 월등히 작으므로 Counting Frequency를 입력할 배열을 생성하여 푸는 것이 입

입력받은 두개의 좌표를 이중배열에 넣고 Comparator를 이용하여 정렬하면 쉽게 풀 수 있다.

두개의 값을 배열 또는 객체를 이용하여 저장 후 첫번째 값만을 비교하여 정렬하면 된다.