[백준/C++] 2565 전깃줄 (G5)

유형	난이도	완료일	링크	특이사항
DP	골드5	23/03/06	https://www.acmicpc.net/board/view/84972

 

 

틀린 코드

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

using namespace std;

int main(int argc, char* argv[]) 
{
	int n;
	cin >> n;
	
	
	vector<pair<int, int>> vec;
	
	int l,r;
	
	for(int i=0;i<n;i++)
	{
		cin >> l >> r;
		vec.emplace_back(make_pair(l, r));
	}
	
	int num=0;
	sort(vec.begin(), vec.end()); // first 기준으로 정렬
	
	while(true)
	{
		int size = vec.size();
		int sum[2][100] = {0, };
		
		

		for(int i= 0; i<size; i++)
		{
			for(int j = i+1; j<size; j++)
			{
				if(vec[j].second < vec[i].second)
					sum[0][i]++;
			}
		}
		for(int i = size-1; i>=0; i--)
		{
			for(int j = i-1; j>=0; j--)
			{
				if(vec[j].second > vec[i].second)
					sum[1][i]++;
			}
		}

		int max = 0;
		int max_idx = 999;
		for(int i= 0; i<size; i++)
		{
			if(max < sum[0][i]+sum[1][i])
			{
				max = sum[0][i]+sum[1][i];
				max_idx = i;
			}
		}

		if(max==0)
			break;
		else
		{
			vec.erase(vec.begin()+max_idx);
			num++;
		}		
	}
	
	cout << num;
}

처음엔 중복이 가장 많은 전깃줄을 순서대로 없애는 방식으로 구현했다. 중복 횟수는 LIS를 구하듯 left쪽 번호 기준으로 정렬 후, ‘나보다 뒤에 있는데 right숫자 값이 작은 요소’ 개수만큼 ++, ‘나보다 앞에 있는데 right 숫자 값이 큰 요소 만큼 sum 배열을++하여 합이 가장 큰 요소를 가장 중복 횟수가 많은 지점으로 선정했고, 우선적으로 제거한 후 다시금 중첩 지점이 있는지 검사하였다.

그러나 중복 횟수가 겹치는 경우가 있을 때 어떤 전깃줄부터 제거하는지에 따라 답이 달라지는 문제가 있었다.

정답 코드

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

using namespace std;

int main(int argc, char* argv[]) 
{
	int n;
	cin >> n;
	
	
	vector<pair<int, int>> vec;
	
	int l,r;
	
	for(int i=0;i<n;i++)
	{
		cin >> l >> r;
		vec.emplace_back(make_pair(l, r));
	}
	
	int num=0;
	sort(vec.begin(), vec.end()); // first 기준으로 정렬
	
	int sum[100] = { };
		
	sum[0] = 1;
	
	int arr[n] = {};
	
	for(int i= 0; i<n;i++)
		arr[i] = vec[i].second;
	
	
	for(int i= 1; i<n;i ++)
	{
		int MAX = 0;
		
		for(int j =i-1; j>=0; j--)
		{
			if(arr[j]<arr[i] && sum[j] > MAX)
				MAX = sum[j];
		}
		sum[i] = MAX + 1;
	}
	
	int ans = 0;
	for(int i=0;i<n;i++)
	{
		if(sum[i]>ans)
			ans = sum[i];
	}
	
	cout << n - ans; 	

}

두 번째 풀이는 최대로 많이 겹치는 선을 제거하는 것이 아니라 결국 LIS문제라는 점에서 “n - LIS(길이)”가 정답이 될 것이라는 추론을 해서 풀었다. 문제 분류에서 LIS응용 문제라는 힌트를 얻지 못했다면 해결에 더 오랜 시간이 걸렸을 것 같다.

첫 번째 풀이와 마찬가지로 left기준으로 정렬한 후 right 쪽에서 가장 긴 증가하는 부분수열의 길이(LIS)를 찾았고 그 길이만큼이 결국 전선이 겹치지 않을 수 있는 가장 긴 길이일 것이므로 전체에서 그 길이를 빼서 정답을 구했다.

응용문제여서 그런지 확실히 실제 해법보다 어렵게 접근했던 것 같다.