#2565번 전깃줄 (C++)

링크 : www.acmicpc.net/problem/2565

2565번: 전깃줄

문제 풀이는 다음과 같다. 

1. 잘라야 하는 전깃줄이 아닌 남겨둬야하는 전깃줄에 초점을 맞춘다.

2. 결국 '오름차순'으로 연결된 전깃줄들의 최대값이 살아남게 되고, 

전체 전깃줄의 갯수에서 최대값을 제외한 값들은 제거하게 된다.

3. 이를 통해 제거해야하는 전깃줄에 갯수를 구한다.

 

이 문제는 백준 11053번 가장 긴 증가하는 부분 수열의 연장판이다.

 

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

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n = 0, max = 0;
	cin >> n;
    int *sum = new int[n];
	vector<pair<int,int>> v;
	for(int i=0; i<n; i++){
		int a, b = 0;
		cin >> a >> b;
		v.push_back(make_pair(a,b));
	}
	for(int i=0; i<n; i++) sum[i] = 1;
	sort(v.begin(), v.end());
	for(int i=1; i<v.size(); i++){
		for(int j=0; j<i; j++){
			if(v[i].second>v[j].second){
				if(sum[i]<sum[j]+1) sum[i] = sum[j]+1;
			}
		}
	}
	for(int i=0; i<v.size(); i++){
		if(sum[i]>max) max = sum[i];
	}
	cout << v.size()-max << "\n";
	return 0;
}

동적할당을 통해 배열을 생성하였으나, 애초에 최대 배열의 크기 500개가 그다지 큰 값이 아니여서

메모리 차이는 없다.

위는 동적할당, 아래는 sum[501]로 생성