[백준] 2352-반도체 설계(C++)

문제링크: https://www.acmicpc.net/problem/2352

2352번: 반도체 설계

 

꽤나 애를 먹었습니다.

문제를 읽고 dp문제인 것을 인지했습니다. 

이 문제는 dp알고리즘 중에서도 LIS( Longest Increasing Subsequence) 입니다.

최대 부분 증가 수열이라고도 합니다.

 

 

만약 

10 20 40 30 70 50 60  의 배열이 있을때

 

10 20 30 50 60 이 최대 부분 증가 수열로써 가장 길이가 깁니다.

아래와 같은 뉘앙스로 해결해주면 됩니다.

#include <iostream>
using namespace std;

struct info {
	int count;
	int port_num;
};
int n,result=0;
struct info dp[40001];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> dp[i].port_num;

	dp[1].count = 1; //초기값 설정

	for (int i = 2; i <= n; i++) {

		for (int j = i - 1; j > 0; j--) {
			if (dp[i].port_num > dp[j].port_num &&dp[i].count < dp[j].count)
				dp[i].count = dp[j].count;
		}
		dp[i].count++;
		if (result < dp[i].count)
			result = dp[i].count;
	}
	cout << result << endl;
}

 
하지만 문제가 생깁니다. 위의 알고리즘은 O(n^2)을 가지게 됩니다.

 

이 문제에서는  n(1 ≤ n ≤ 40,000) 입니다. 즉, 최악의 경우에 O(n^2) = 40000 X 40000 = 1,600,000,000 이 되기 때문에 시간제한 2초로는 어림도 없죠 ( 1억번 연산 당 대략 1초)

 

즉 O(n) or O(nlgn)의 풀이법을 찾아야합니다. 해당 문제에서 이전값들을 비교해서 결과를 도출해야 하기 때문에 O(n)은 불가능합니다.

 

C++ stl에서 제공하는 기능은 1.Lower Bound 2.인덱스 트리 입니다. (정확한 메소드내용은 모르겠지만 탐색시 O(lgn)번의 탐색으로 위치를 전달합니다. 

 

함수들에 관한 자세한 설명은  출처:https://dyngina.tistory.com/16

LIS (Longest Increasing Subsequence)

 

 

제가 만든 정답 코드입니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n = 0,len=1;
int arr[40001] ;
int arr2[40001] = { 0 };
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	arr2[len] = arr[1]; //초기값 설정
	
	for (int i = 2; i <= n; i++) {
		if (arr2[len] < arr[i]) {
			arr2[++len] = arr[i];
		}
		else {
			int val = lower_bound(arr2 + 1, arr2 + len + 1, arr[i]) - arr2;
			arr2[val] = arr[i];
		
		}
		
	}
	
	cout << len << endl;
}

생각해보니 arr는 필요가 없더군요 매번 값을 입력받고 arr2에 저장해주면 됩니다.

그리고 lower_bound메소드의 역할을 이분탐색을 통해서 구현을 할 수 도 있겠군요.

 

 

 

#include <stdio.h>
#define M 40010
int port[M];
int up[M] = { 0x80000001, };
int ref[M];
int n, max;

int search(int left, int right, int x) {
	int mid;

	if (left > right) return left;

	mid = (left + right) / 2;

	if (ref[mid] < x)
		return search(mid + 1, right, x);
	else if (ref[mid] > x)
		return search(left, mid - 1, x);
	else
		return mid;
}

int main() {
	int i, cursor;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", port + i);
		cursor = search(0, max, port[i]);
		ref[cursor] = port[i];
		up[i] = cursor;
		if (cursor > max)
			max = cursor;
	}
	printf("%d\n", max);
	return 0;
}