자바시작 워니

풀이 과정 처음에는 입력값도 크고 그래서 잠시 유니온파인드인가? 라는 착각을 했었다.. 근데 그러한 문제는 아닌거 같고 그냥 DFS로 풀어보기로 했다. 여기서 핵심은 임의의 두 섬 a와 b에 대해, a번 섬에서 b번 섬으로 직접 이동할 수 있는 다리와 b번 섬에서 a번 섬으로 직접 이동하 룻 있으면, 두 섬은 연합을 결성하는 것이다. 그리고 주의해야할 점으로 a와 b가 연합을 결성하고 b와 c가 여합을 결성했다면 a와 c 역시 위 조건을 만족하지 않더라도 같은 연합에 속해있다고 보는 것이다. 따라서 예제 2번에서 1이 출력되는 것이다. static int count = 0; static boolean visited[]; static ArrayList[] graph; 먼저, static 필드로는 count..

풀이 과정 먼저 노드들의 연결 정보를 담기 위해서 ArrayList[] graph를 선언하였다. 그리고 노드 개수만큼 반복하여 해당 인덱스마다 해당 노드가 연결된 정보를 담을 수 있게 new ArrayList();를 통해 할당하였다. 그리고 visited를 통해서는 해당 노드를 방문했을 경우 다음 노드를 방문할 수 있는 용도로 정의하였다. 그 후에 간선의 개수만큼 순회하며 입력된 간선의 정보를 통해 양 노드가 서로 연결되어 있기 때문에 양 노드 모두 해당 인덱스에 대한 ArrayList에 추가하도록 작성했다. 문제 조건 중에 방문할 수 있으면서 번호가 가장 작은 노드로 이동하기 때문에 해당 노드에 연결된 노드들을 오름차순으로 정렬했다. DFS 방식을 사용하여 시작 노드로부터 연결된 노드들을 순회하면 위에..

풀이 과정 먼저, 이 문제는 Dynamic Programming으로 해결할 수 있다. 예를 들어, 3, 4, 5 힐 아이템이 있다고 가정하고, 9라는 통증을 0으로 만들어야하는 상황을 가정해보자. 그 때, 3원의 동전으로 통증 3을 해결하는 방법은 1가지이고, 통증 6을 해결하는 방법은 통증 (6 - 3)을 해결하는 경우의 수 + 1 즉, 2가 된다. 그리고 마지막 통증 9를 해결하기 위해서는 통증 (9 - 3)을 해결하는 방법 + 1이 된다. 다시 4원과 5원을 봤을때 통증 4를 해결하는 방법, 통증 5를 해결하는 방법은 각각 1가지가 되고, 통증 9를 해결하는 방법은 통증 (9 - 4)를 해결하는 방법 + 1(본인) 즉, 2가지가 필요하다. 따라서 정답은 2가 된다. 이를 순서대로 다시 작성해보자. ..