[0625] 알고리즘

2565. 전깃줄
가뜩이나 문제를 늘 늦은 시간에 푸는데 오늘은 정말 늦게 잡아서... 어제 문제의 연장선 문제인 전깃줄 문제를 풀었다. 어제와 똑같은 다이내믹 프로그래밍 + LIS 문제로 코드 자체는 어제와 똑같은데, 먼저 배열을 pair로 입력받고 first 기준으로 정렬한다. 그리고 second를 기준으로 LIS의 길이를 구해 전체 전깃줄 개수에서 뺀다.

#include <iostream>
#include <algorithm>
#include <vector>
int main() 
{ 
	std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);
    int n, num1, num2;
    
    std::cin >> n;
    std::vector<std::pair<int, int>> pair;
    std::vector<int> memory(n, 1);
    
    for (int i = 0; i < n; i++)
    {
    	std::cin >> num1 >> num2;
        pair.push_back(std::make_pair(num1, num2)); 
    }
    
    std::sort(pair.begin(), pair.end());
    
    for (int i = 0; i < n; i++)
    { 
    	for (int j = 0; j < i; j++)
        {
        	if (pair[j].second < pair[i].second)
            {
            	memory[i] = (memory[i] > memory[j] + 1 ? memory[i] : memory[j] + 1);
            }
        }
    }
    
    int max = * std::max_element(memory.begin(), memory.end());
    std::cout << (n - max) << '\n';
    return 0;
}

알고리즘 헤더 파일을 이용해 sort를 수행한 부분이 추가되었을 뿐 전체적인 흐름은 어제와 똑같다.

내일은 진짜로 LIS를 더 효율적으로 구하는 방법을 알아볼 것...