[백준] 1365번 꼬인 전깃줄 - C++

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

1365번: 꼬인 전깃줄

문제

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

출력

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

---

     전선이 꼬이지 않으려면 왼편을 기준으로 연결된 오른편의 전깃줄 번호가 증가하는 수열을 이루어야 한다. LIS 알고리즘을 사용해야 하는데 N이 100,000 이기 때문에 O(nlogn) 알고리즘을 활용해야 한다. c++에서 lower_bound는 이분 탐색을 활용하여 값을 찾기 때문에 해당 함수를 활용하여 답을 구할 수 있다. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define MAX 1000010

using namespace std;

int N;
int arr[MAX], dp[MAX], memo[MAX];
stack <int> ans;
int len = 0;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	
	dp[len++] = arr[0];
	for (int i = 1; i < N; i++) {
		if (arr[i] > dp[len - 1]) {
			dp[len++] = arr[i];
		}
		else {
			int* iter = lower_bound(dp, dp + len, arr[i]);
			*iter = arr[i];
		}
	}
	cout << N - len;
	return 0;
}

---

    문제를 보고 O(nlogn) 의 시간이 소요되는 LIS 알고리즘을 사용해야겠다고 바로 생각했지만 이분 탐색을 활용하는 알고리즘이 잘 기억나지 않아서 이전에 포스팅했던 LIS알고리즘을 참고하였다. DP 그리디 BFS와 같이 유명한 알고리즘은 많이 사용하여서 익숙해졌는데 이런 알고리즘들은 유명하지만 많이 사용을 안 하다 보니 LIS를 사용하면 되겠다 까지만 생각이 나고 직접 코드는 생각이 안나는 것 같다. 감이 무뎌지기 전에 자주자주 풀어봐야겠다.