Coding 한놈만 팬다

문제링크 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 문제 풀이 과정 동전문제는 그리디 문제로 많이 알려져 있지만, 이 문제는 그리디로 접근 하면 해결이..

문제링크 문제 풀이 과정 크루스칼 풀이 방법을 그대로 적용하면 되는 문제이다. 크루스칼을 적용하기 전에 한단계 준비 작업이 필요하다. 주어진 데이터는 별들의 좌표만 주어지기 때문에 서로 다른 별들의 거리를 먼저 구한 다음 크루스칼을 적용하면 된다. 두점 사이의 거리 구하는 방법이다. public static double dist (Point p1, Point p2){ return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); } 별들의 좌표는 Point class 를 별도로 구현하였다. public static class Point{ double x; double y; int idx; public Point(double x, double..