알고리즘: 백준 2565번 전깃줄 (feat. c++) 최장증가수열문제(LIS)

백준 2565번 문제입니다. 

2565번: 전깃줄

 

 

좀 꼬아놓은 최장증가 수열 문제

(사실 최장증가수열문제는 처음 접해보았다...)

 

 

처음에는 파이썬으로 스택을 이용해서 풀었지만 무슨 이유인지 틀렸다고 나왔다...

 

(틀린 코드)

n = int(input())
line_list = []
for i in range(n):
    line_list.append(list(map(int, input().split())))


del_count = 0

while True:
    cross = []
    for i in range(len(line_list)):
        count = 0
        for j in range(len(line_list)):
            if (line_list[i][0] - line_list[j][0]) * (line_list[i][1] - line_list[j][1]) < 0:
                count += 1
        cross.append([i, count])
        cross.sort(key=lambda x: -x[1])
    del line_list[cross[0][0]]
    cross.pop(0)
    del_count += 1

    if cross[0][1] == 0:
        break

print(del_count - 1)

 

 

 

 

 

 

그래서 마음을 다시 잡고 이번에는 c++로 접근하였다.

 

하지만 c++은 파이썬보다 미숙해서 구글의 도움을 받았고 

 

최장증가 수열 문제임을 알고 접근하였다. 

 

 

 

문제의 해결의 키는 다음과 같다.

 

겹치는 전깃줄을 최소한으로 제거함으로써 전깃줄이 겹치지 않게 해야한다.

 

그래서 전깃줄 리스트 cable을 받아 cable[0][0] ~ cable[N-1][0] 까지  1열을 기준으로 오름차순 정렬한 후

 

cable의 1열을 오름차순 정렬시키고 cable 2열에서 최장 증가 수열을 구한다. 

 

 

 

예를 들어 

 

1 8

3 9

2 2

4 1

6 4

10 10

9 7

7 6

 

라는 입력을 받았을 때

 

 

 

1열을 기준으로 정렬 시킨다면 

 

 

1 8

2 2

3 9

4 1

6 4

7 6

9 7

10 10

 

위와 같이 된다.

 

 

 

이번에는 2열을 기준으로 최장증가수열을 구하면

 

4 1

6 4

7 6

9 7

10 10

 

또는

 

2 2

6 4

7 6

9 7

10 10

 

이다.

 

 

 

최장증가수열의 크기를 구하는 과정에는 다음과 같이 다이나믹 프로그래밍이 사용된다.   

 

이 때 dp[i]는 arr[i]로 끝날때 최장 증가수열의 길이를 의미한다. 

 

int dp[10] = {0} //10이라고 해보자

	int max_num = 0; //가장 긴 증가 수열의 길이
    
	for (int i = 0; i < 10; i++) { 
    
		dp[i] = 1;
        
		for (int j = 0; j < i; j++) {
        
			if (arr[i] > arr[j] && dp[i] < dp[j] + 1) // dp값을 이어가야 하므로 
				dp[i] = dp[j] + 1;
		
		}

 

 

 

 

코드를 보면 다음과 같다. 

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;


int main() {

	int N;  
	scanf("%d", &N);
	vector<vector<int>> cable;  //이차원 벡터이므로
    
    
	for (int i = 0; i < N; i++) {  // 이차원 벡터를 만들어주는 과정
		vector<int> tmp;
		int a, b;
		cin >> a >> b;
		tmp.push_back(a);
		tmp.push_back(b);
		cable.push_back(tmp);
	}
    
    
	sort(cable.begin(), cable.end());
    //1열을 기준으로 오름차순 배열 (이건 처음 알았다)



	int dp[100] = { 0 };
    //최장증가수열을 쓰기 위해 동적프로그래밍을 이용한다.

	int max_num = 0;
	for (int i = 0; i < N; i++) {  //최장증가수열을 구하는 과정 
		dp[i] = 1;
        
		for (int j = 0; j < i; j++) {
			if (cable[i][1] > cable[j][1] && dp[i] < dp[j] + 1)
				dp[i] = dp[j] + 1;
		
		}
        
		max_num = max(max_num, dp[i]);
		
	}
    
	printf("%d", N - max_num);
	
	return 0;
}

 

최장증가 수열 잘 기억해두자