이분탐색으로 중량을 정해두고 BFS로 다리를 지나갈 수 있는지 확인하면 쉽게 풀리는 문제이다.
이렇게 풀 경우 서로 같은 두 도시 사이에 여러 개의 다리가 있다는 조건을 딱히 생각해 줄 필요가 없다.
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner in = new Scanner(System.in);
int v = in.nextInt();
int e = in.nextInt();
LinkedList<Bridge> bridges[] = new LinkedList[v + 1];
for (int i = 1; i <= v; i++) {
bridges[i] = new LinkedList<Bridge>();
}
int max = 0;
for (int i = 0; i < e; i++) {
int start = in.nextInt();
int end = in.nextInt();
int size = in.nextInt();
max = Math.max(max, size);
bridges[start].add(new Bridge(end, size));
bridges[end].add(new Bridge(start, size));
}
int start = in.nextInt();
int end = in.nextInt();
System.out.println(findMinimumWeight(start, end, bridges, max));
}
publicstaticintfindMinimumWeight(int from, int to, LinkedList<Bridge> bridges[], int end){
boolean[] isVisited = newboolean[bridges.length];
int start = 0;
int max = 0;
while (start <= end) {
int mid = (start + end) / 2;
if (BFS(from, to, bridges, mid, isVisited)) { // 가능하니까 일단 결과 저장 후 중량을 더 늘려보자
max = Math.max(max, mid);
start = mid + 1;
} else {
end = mid - 1;
}
}
return max;
}
publicstaticbooleanBFS(int start, int end, LinkedList<Bridge> bridges[], int maxSize, boolean[] isVisited){
clearVisit(isVisited);
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(start);
isVisited[start] = true;
while (!queue.isEmpty()) {
int now = queue.poll();
if (now == end) {
returntrue;
}
for (Bridge bridge : bridges[now]) {
if (!isVisited[bridge.destination] && maxSize <= bridge.size) {
queue.add(bridge.destination);
isVisited[bridge.destination] = true;
}
}
}
returnfalse;
}
publicstaticvoidclearVisit(boolean[] isVisited){
Arrays.fill(isVisited, false);
}
}
classBridge{
int destination;
int size;
publicBridge(int destination, int size){
this.destination = destination;
this.size = size;
}
@Overridepublicbooleanequals(Object o){
Bridge bridge = (Bridge) o;
return destination == bridge.destination;
}
@OverridepublicinthashCode(){
return Objects.hash(destination);
}
}
출발지점부터 distance 사이에 바위를 제거했을 때, 제거한 바위의 최솟값 중에 가장 큰 값을 구하는 문제이다.
이 문제는 바위를 제거하는 모든 경우를 구한 후 최솟값을 구한다면,
바위가 N개, R개를 제거할 수 있다면 O(NCR)로 시간초과가 발생하게 된다.
이러한 경우에는 바위를 제거하는 모든 경우의 수를 구하기보다는,
바위간의 최소 거리를 정해두고 이 조건이 가능한지 여부를 보는 쪽으로 생각하면 된다.
바위간의 최소 거리를 정할 때에는 이분 탐색을 사용하도록 했다. 풀이 방식은 아래와 같다.
1. 이분 탐색으로 최대 사잇값 diff를 정한다.
2. 돌을 n개 지웠을 때 최소 거리가 diff인지 확인한다.
=> 즉, 돌 사이의 거리가 diff보다 작으면 돌을 없애고,
최종적으로 없애야 하는 돌의 수가 n보다 크면 diff를 너무 크게 잡은 것이므로 왼쪽을 탐색하도록 한다.
classSolution{
publicintsolution(int distance, int[] rocks, int n){
int length = rocks.length;
int start = 0;
int end = distance;
int answer = 0;
Arrays.sort(rocks);
while (start <= end) {
int mid = (start + end) / 2;
if (!isPossible(rocks, n, length, mid, distance)) {
// diff가 너무 크니까 줄이자
end = mid - 1;
} else { // 가능하니까 일단 answer에 저장하고 더 늘려보자
answer = Math.max(answer, mid);
start = mid + 1;
}
}
return answer;
}
publicbooleanisPossible(int[] rocks, int n, int length, int diff, int distance){
int remove = 0;
int before = 0;
for (int i = 0; i < length; i++) {
if (rocks[i] - before < diff) { // diff보다 작으니 돌을 없애자
remove++;
} else {
before = rocks[i];
}
if (remove > n) { // 돌을 n개보다 더 없애야 하는 경우returnfalse;
}
}
if (distance - before < diff) {
remove++;
}
return remove <= n;
}
}
=> O(N^2), N ≤ 100000이므로 1초안에 통과될 수 없다. 아마 10초정도 걸릴것임...ㅠㅠ
dp[n]: n번째 수를 마지막으로 하는 최장증가부분수열로 정의했다.
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int[] stock = newint[n];
int[] dp = newint[n];
int max = 0;
for (int i = 0; i < n; i++) {
stock[i] = in.nextInt();
}
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (stock[i] > stock[j]) {
dp[i] = Math.max(dp[j], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
}
}
2차 시도 - N ≤ 100000이므로 1초안에 통과하려면 시간복잡도가 적어도 NlogN을 되어야 한다. => `이분탐색`을 이용한다
stock 수열을 처음부터 보면서
1. dp의 끝 값과 비교했을 때 마지막 값보다 큰 경우 dp의 마지막에 바로 삽입
2. dp의 끝 값과 비교했을 때 마지막 값보다 작거나 같은 경우 이분탐색을 이용하여 LIS를 유지하기 위한 위치에 수를 삽입하도록 한다.
https://www.acmicpc.net/problem/3745 예제
stock[0]을 dp 리스트에 넣는다.
stock[1]이 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=0)
stock[2]가 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=0)
stock[3]은 1보다 크므로 바로 삽입
stock[4]는 4보다 크므로 바로 삽입
stock[5]가 어디에 삽입될 수 있는지 인덱스를 이분탐색을 이용하여 구한다. (index=1)
예제에서 볼 수 있듯이 최종 dp 수열은 진짜 최장 증가 부분 수열을 이루는 요소와는 상관 없으며, lis의 길이만 연관이 있다는 점이 중요하다
위 알고리즘을 적용하여 코드를 짜 보면 아래와 같다.
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int[] stock = newint[n];
int[] dp = newint[n];
for (int i = 0; i < n; i++) {
stock[i] = in.nextInt();
}
dp[0] = stock[0];
int lastIndex = 0;
for (int i = 1; i < n; i++) {
if (dp[lastIndex] < stock[i]) {
lastIndex++;
dp[lastIndex] = stock[i];
} else {
int index = findIndex(dp, stock[i], lastIndex);
dp[index] = stock[i];
}
}
System.out.println(lastIndex + 1);
}
}
publicstaticintfindIndex(int[] dp, int num, int lastIndex){
int left = 0;
int right = lastIndex;
while (left < right) {
int mid = (left + right) / 2;
if (dp[mid] == num) {
return mid;
}
if (dp[mid] > num) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
}
다른 방법으로는 `segment tree`를 사용하는 방법도 있다. segment tree를 사용하여 lis 길이를 구하는 방법은 아래와 같다.
1. 세그먼트 트리를 모두 0으로 초기화한다. , (stock[i], i) 객체를 만든 후 stock[i] 값에 대해 오름차순으로 정렬한다.
2. (stock[i], i)를 순회하면서 stock[i]에 대해구간 [0, i]에서 최댓값을 구하고, 그 최대값+1을 세그먼트 트리의 인덱스 i인 리프 노드 값으로업데이트한다. => i에 대해 구간 [0, i]에 지금까지 존재하는 LIS 길이+1 은 결국 stock[i]으로 끝나는 LIS길이와 같다.
3. 정렬된 객체를 순회하면서 LIS의 max 값을 찾는다.
가장 먼저 stock[i]=1인 i=2를 방문하게 된다.
먼저 구간 [0, 2]의 최댓값은 0이므로 1로 끝나는 LIS 길이는 1이고,
그 1 값을 인덱스 2에 업데이트 해 준다.
그 다음 stock[i]=2인 i=1를 방문하게 된다.
마찬가지로 [0, 1]의 최댓값은 0이므로 인덱스 1에 업데이트 해준다.
이때, 기존 LIS 결과가 증가하지는 않는다.
일단 이후 값이 언제 증가되는지 좀 더 보기로 하자.
그 다음 stock[i]=3인 i=5를 방문하게 되는데,
[0, 5]의 최댓값은 1이므로 인덱스 5에 2를 업데이트 해준다.
즉, 새로 보는 원소가 기존의 LIS 길이를 증가시키려면
그 원소가 기존의 LIS보다 뒤에 나타나야 한다.
=> 이를 확인하는 것이 결국 구간 [0, i]의 최댓값을 보는 것이다.
이렇게 세그먼트 트리를 이용하여 stock[i]의 위치에 i번째 수를 마지막 원소로 가지는 lis의 길이를 업데이트함으로써 lis의 가장 긴 길이를 구할 수 있다.
