백준 2352 : 반도체 설계

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

2352번: 반도체 설계

 

줄이 꼬이지 않기 위해선 연결하는 줄의 번호가 증가하는 수열로 이루어지면 되므로 LIS로 풀 수 있는 문제다.

다만 일반적인 LIS는 O(n^2)의 시간복잡도를 갖는데, 이 문제의 경우 포트가 최대 4만개이므로 n^2은 시간 초과가 발생한다. O(nlogn)의 시간복잡도를 갖는 LIS는 아래와 같이 그리디 기법으로 구현할 수 있다.

 

#include <iostream>
#include <algorithm>

#define max(a,b) a>b?a:b
using namespace std;

int n;
int arr[40'000];
int lis[40'000];

int LIS() {
	int idx = 0, target;
	lis[0] = arr[0];
	for (int i = 1; i < n; i++) {
		//현재 포트가 가장 최근에 연결한 포트 번호보다 커서 줄이 꼬이지 않는 경우
		if (lis[idx] < arr[i]) {
			lis[++idx] = arr[i];
		}
		//줄이 꼬이는 경우 이전에 연결한 포트를 재조정
		//현재 포트 번호보다 큰 값들 중 가장 작은 값을 현재 포트 번호로 바꿔줌
		//-> 줄이 꼬이지 않는 한도 내에서 최고의 선택
		else {
			target = lower_bound(lis, lis + idx, arr[i]) - lis;
			lis[target] = arr[i];
		}
	}
	return idx + 1;
}

void solution() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	cout << LIS();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2332 kb

시간: 4 ms

 

nlogn 풀이는 아래 블로그를 참고했다.

https://jaimemin.tistory.com/488

백준 2352번 반도체 설계

https://dyngina.tistory.com/16

LIS (Longest Increasing Subsequence)