BOJ 1365: 꼬인 전깃줄

https://www.acmicpc.net/problem/1365

---

알고리즘 분류 | 가장 긴 증가하는 부분 수열 (LIS), Lower bound 알고리즘

풀이 |

일반적인 LIS 알고리즘으로 풀었더니 시간 초과가 나서 새로운 알고리즘을 찾아보았다.

검색 결과 LIS 알고리즘 중에서도 Lower bound 방법으로 풀어야 한다고 했다.
이 알고리즘은 숫자가 입력될 때마다 벡터의 값을 비교하여 Lower bound로 찾은 인덱스에 있는 값을
교체해주는 알고리즘이다.

즉, 쉽게 설명하면 새로운 숫자가 들어올 때마다 세 가지 경우로 나누어 입력한다.
1. 벡터가 비어있어서 그냥 수를 추가하는 경우
2. 제일 끝 값과 비교하여 더 큰 값이 들어온 경우, 그냥 맨 마지막에 추가한다.
3. 제일 끝 값보다 작은 값이 들어온 경우, Lower Bound 알고리즘으로 반환된 index에 값을 교체한다.

간단히 그림으로 설명할 수 있다.
n = 8, 입력이 7 8 1 2 9 3 4 6 인 경우

이런 순서로 입력되며, 초록색인 경우가 그냥 추가되는 경우이고
주황색인 경우가 Lower Bound를 호출하며 index 값에 교체되는 경우이다.

답을 출력하기 위해 n에서 제일 긴 증가하는 수열의 크기를 빼고 출력하였다.
제일 큰 증가하는 수열을 제외한 나머지 전깃줄을 잘라야 하는 것이 답이기 때문이다.

소스 코드 |

// LIS lower bound 알고리즘
#include <iostream>
#include <vector>
using namespace std;

vector<int> v;

int lower(int num) {
	int low = 0, high = v.size() - 1;

	while (low < high) {
		int mid = (low + high) / 2;
		if (v[mid] >= num)
			high = mid;
		else
			low = mid + 1;
	}

	return high;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;

		if (v.empty())
			v.push_back(temp);
		else if (v[v.size() - 1] < temp)
			v.push_back(temp);
		else
			v[lower(temp)] = temp;
	}

	cout << n - v.size() << '\n';
	return 0;
}

관련 문제 및 참고 자료 |

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence) https://seungkwan.tistory.com/8
알고리즘 기초 - Lower Bound & Upper Bound https://blog.naver.com/bestmaker0290/220820005454
BOJ 2565: 전깃줄 https://www.acmicpc.net/problem/2565