[백준 BOJ 11053 silver4 - 가장 긴 증가하는 부분 수열] Longest Incresing Subsequence (LIS)

백준 11053 가장 긴 증가하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

 

어떤 수열이 주어졌을 때, 가장 긴 증가하는 부분수열의 길이를 출력하는 문제이다.

 

dp[N] 배열을 선언하고, dp[N]에는 N번째 수를 마지막 원소를 갖는 가장 긴 증가하는 부분수열(lis)의 길이를 저장한다.

 

O(N^2)으로 푼다.

이중 포문을 돌면서, 현재 수보다 1 작은 수까지 돌면서 그중에서 찾은 lis의 최대 길이 + 1 을 현재 수 배열에 저장한다.

 

마지막 dp배열에서 가장 큰 수가 lis의 최대 길이가 된다.

 

for (int i = 1; i <= N; i++) {
		for (int k = 1; k < i; k++) {
			if (num[i] > num[k]) {
				lis[i] = max(lis[k]+1, lis[i]);
			}
		}
	}

num 배열 : 주어진 수 배열

lis 배열 : 각 수를 마지막 원소로 갖는 lis의 최대 길이 저장

 

 

lis응용하기 - 백준 2565 전깃줄

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

2565번: 전깃줄

 

꼬인 전깃줄이 없게 전깃줄을 자르는데, 자르는 전깃줄의 개수가 최소가 되도록 해야 한다.

전깃줄이 꼬이지 않으려면 왼쪽에서 숫자가 더큰(그림 상에서 더 아래 있는) 전봇대는 오른쪽에서도 더 큰 숫자의 전봇대와 이어져야 한다. 

 

즉, 왼쪽 전봇대의 수가 오름차순이 되도록 정렬했을 때, 오른쪽 전봇대의 수 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하면 그 길이가 자르지 않아도 되는 전봇대의 개수가 된다.