BOJ 1939
BOJ 1939 중량제한 [Java]
BOJ 1939 중량제한 1. 문제 링크 https://www.acmicpc.net/problem/1939 2. 문제 해설 처음에는 실수로 시간복잡도를 생각 안하고 접근했다. 공장이 있는 섬 두 개 중 한 지점에서 다른 지점까지 갈 수 있는 모든 경로를 살펴보면서 각 경로마다의 최소의 중량제한을 구하고, 그 값의 최대값을 구하는 방식을 dfs로 구현하였다. 시간복잡도가 O(NM)으로 당연히 시간초과가 나왔다. 시간복잡도를 줄일 수 있는 방법이 무엇이 있을까 고민하다가, 각 다리의 중량제한의 범위가 1 ≤ C ≤ 1,000,000,000 으로 굉장히 큰 것을 보고 이분탐색을 떠올렸다. BFS와 이분탐색을 이용해서 풀 수 있는데, 각 로직의 흐름을 설명해보겠다. 이분탐색 로직 이분탐색을 할 대상은 물품의 중..