백준 2556번 전깃줄(C++)

문제

정답 코드

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


int N;
vector<pair<int,int>> input;
int ret= 0;
int DP[101];
int max_size=0;
int calcDp(int i){
	int now_num = input[i].second;
	int calc_ret=1;
	for(int j=0; j <i;j++){
		if (input[j].second < now_num)
			calc_ret = max(DP[j]+1,calc_ret);
	}
	max_size = max(max_size, calc_ret);
	return calc_ret;
}

int main(){
	cin >> N;
	int a,b;

	for(int i=0;i<N;i++){
		cin >> a >> b;
		input.push_back({a,b});
	}
	DP[0] = 1;
	sort(input.begin(),input.end());
	for(int i=1;i<N;i++) DP[i] = calcDp(i);
	cout << N-max_size << "\n";
}

문제 풀이의 흐름

정렬 후 증가하는 부분 수열로 풀면 된다.

문제를 먼저 설치 후 지우는게 아니라 설치 가능한 전깃줄의 최대 갯수를 구하면 된다.

이건 정렬을 시키고나면, 작은 순서부터 존재하기 때문에 거기에서 작은 숫자부터 연속되는 부분수열을 구하면 설치할 수 있는 모든 수열을 만들 수 있다는 개념이 핵심이다.

주의 할 점

아이디어가 잘 안 떠올라서 그리디로 해결할 수 있지 않을까라는 추측을 했었다.

DP가 한번에 보인다면 당신은 개고수!

반성 및 고찰

ㅠㅠ 그리디로 풀다가 코드가 더럽고 자료구조에 제대로 안 담긴다면 다시 생각해보는 습관을 가져봐야겠다.

대체로 그리디는 DP와 많이 헷갈리니 하드코딩 느낌이 든다면 DP 풀이를 떠올리도록 해야할 것 같다.

오답코드

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

//생각 -> 가장 많은 전깃줄과 겹치는 전깃줄을 없애면 되지 않을까?
// 예제 
// 겹치는 것을 지우는 기준 지우는 점을 (a,b)고 비교대상을 (A,B)라고 할 때
// (a>b && b<B) || (a<b && b>B) 일 때 겹친다고 판단
// (1,8)=5, (2,2)=2, (3,9)=4, (4,1)=3, (6,4)=2, (7,6)=2, (9,7)=2, (10,10) = 0
// (1,8)X =>(2,2)=1, (3,9)=4, (4,1)=2, (6,4)=1, (7,6)=1, (9,7)=1
// (3,9)X =>(2,2)=1		   (4,1)=1, (6,4)=0, (7,6)=0, (9,7)=0
// (2,2)X => 0,0,0,0,0
//답 : 3개
//

int N;

typedef struct s_input{
	int a;
	int b;
	int cnt;
}t_input;

vector<t_input> arr;
int next_max=0;
int next_idx=-1;
int calc(int a,int b){
	int cnt =0;
	for(int i=0;i<N;i++){
		if ((a < arr[i].a && b > arr[i].b) || (a > arr[i].a && b < arr[i].b))
			cnt++;
	}
	return (cnt);
}

int main(){
	cin >> N;
	int a,b;

	for(int i=0;i<N;i++){
		cin >> a >> b;
		t_input x;
		x.a=a; x.b=b; x.cnt = 0;
		arr.push_back(x);
	}
	for(int i=0;i<N;i++) {
		arr[i].cnt = calc(arr[i].a,arr[i].b);
		if (arr[i].cnt > next_max){
			next_max = arr[i].cnt;
			next_idx = i;
		}
	}
	int ret=  0;
	while (next_idx != -1){
		arr[next_idx].cnt = 0;
		int temp_i = -1;
		int temp_max = 0;
		for(int i=0;i<N;i++){
			if (arr[i].cnt == 0)
				continue;
			if ((arr[next_idx].a < arr[i].a && arr[next_idx].b > arr[i].b) || (arr[next_idx].a > arr[i].a && arr[next_idx].b < arr[i].b))
				arr[i].cnt--;
			if (arr[i].cnt > temp_max){
				temp_max = arr[i].cnt;
				temp_i = i;
			}
		}
		next_idx = temp_i;
		next_max = temp_max;
		ret++;
	}
	cout << ret<<"\n";
}

가장 많은 줄부터 자르는 방식으로 풀려고 하니까, 같은 줄을 자르는 경우가 문제가 된다.

그리디 방식으로 풀때 이 반례가 문제가 된다.

내 코드는 우연히 이런 테스트 케이스도 몇개 통과하지만, 실제론 이런 식의 접근은 틀렸다.

흑흑 LIS 기본 문제인데 쉽게 해결하지 못해서 슬프다.. 하지만 다음에 비슷한 문제가 나오면 풀 수 있을 것 같다 아좌잣!