[JAVA] 백준 1865 - 웜홀 https://www.acmicpc.net/problem/1865특정 정점에서 출발해서 다시 해당 정점으로 돌아왔을 때, 가중치가 음수값인 정점의 존재 여부를 구하는 문제이다. 그리디 기반인 다익스트라는 음수 가중치에서 사용하지 못하고 출발점이 명시되지 않았으므로 모든 정점을 염두에 두어야해서 플로이드 워셜을 선택했다.도로는 양방향으로 입력했고, 웜홀은 단방향으로 입력했다.동일 노선에 여러 경로가 있을 수 있으므로 최소값만 저장하도록 구현했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main { public sta.. 2025. 9. 3. [JAVA] 백준 1238 - 파티 https://www.acmicpc.net/problem/1238한 정점에서 파티가 열리고, 다른 정점에서 해당 정점으로 최단거리로 방문했다가 다시 돌아갈 때, 가중치가 가장 높은 정점의 가중치를 출력하는 문제이다.사실 입력 조건 중 정점의 개수를 100으로 보고 100만번이면 플로이드-워셜 써도 되겠다~ 하고 플로이드로 풀었는데 다시보니 1000이여서 10억번이면 무조건 시간초과를 생각이 들었고 일단 아쉬운 김에 제출해봤는데 통과했다. 정석적인 풀이는 파티가 열리는 정점에서 다익스트라를 돌리고, 간선의 방향을 전부 반대로 해서 다시 다익스트라를 돌리는 것이라고 한다.또 하나 배워갑니다. import java.io.BufferedReader;import java.io.IOException;import j.. 2025. 9. 2. [JAVA] 백준 30805 - 사전 순 최대 공통 부분 수열 https://www.acmicpc.net/problem/30805주어진 두 수열의 공통 부분 수열 중 사전 순으로 가장 뒤에 있는 수열의 길이를 구하는 문제이다.먼저 주어진 수열 중 공통이 아닌 부분을 지웠고, 그 이후 최댓값을 구해 각 수열에 해당 최댓값이 몇번 나오는지 구했다. 각 수열에서 최댓값이 나온 횟수 중 작은 값(min)만큼 부분 수열이 될 수 있으니 정답 문자열에 최댓값을 min번 붙여준 뒤,각 수열에서 해당 최댓값이 min번째 나오는 위치를 구해 해당 위치 기준으로 sublist한 뒤 동일한 처리를 반복해 list가 전부 비어있을 때 탈출하는 방법으로 풀었다. import java.io.BufferedReader;import java.io.IOException;import java.io.. 2025. 9. 2. [JAVA] 백준 9372 - 상근이의 여행 https://www.acmicpc.net/problem/9372 문제를 대충 읽고 가장 적은 종류 -> BFS! 하고 BFS 돌렸다가 깨달은 문제이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea.. 2025. 8. 30. 이전 1 ··· 14 15 16 17 18 19 20 ··· 78 다음