MST2 백준 1368번 : 물대기 (Java) 문제 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 구현 방법 최소의 비용으로 모든 논에 물을 대야하기 때문에 Kruskal 알고리즘을 사용했습니다. 물을 대는 방법은 직접 논에 우물 파는 방법, 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 방법 2개가 있어 적절한 방법을 골라 사용해야 합니다. 처음에는 너무 복잡하게 생각했는데 사실 우물이라는 가상의 노드를 추가하면 해결되는 문제였습니다. 즉, 우물이라는.. 2022. 2. 14. 백준 2887번 : 행성 터널 (Java) 문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 구현 방법 최소 스패닝 문제 이지만!!!!! 주어진 행성의 개수가 100,000개, 모든 행성 간의 거리를 구하면 100,000 * 99,999/2 = 약 500억개 이므로 사용하는 메모리가 메모리 제한인 128MB를 훨씬 초과하게 됩니다. 따라서 다른 방법을 찾아야 했지만 전 찾지 못했고^^ 질문 검색을 참고하여 풀었습니다. 행성을 터널로 연결할 때 드는 비.. 2022. 2. 7. 이전 1 다음
