[boj][c++] 2565 전깃줄

2565 전깃줄

위의 그림에서 엉킨 전깃줄을 풀기 위해 제거해야 되는 최소 전깃줄 개수를 구하는 문제이다.

처음에 문제 이해를 잘못해서 전깃줄을 짝에 맞게 정렬하기 위해 연결해야 하는 최소 개수를 구하는 문제라고 생각했다. 그런데 내 생각보다는 간단한 문제였음ㅎ

식을 생각해내는건 금방 해냈지만 구현이 감이 안 잡혔다. vector컨테이너로 자료 받고 프로그래밍이 멈춰서 결국 다른 사람들의 풀이를 참고하여 풀었다. dp를 사용

로직은 다음과 같다.

• 왼쪽 전봇대의 전깃줄을 기준으로 오른쪽 전봇대의 전깃줄을 정렬한다.
• 정렬한 전깃줄 중 가장 긴 오름차순 배열의 개수를 구한다.
• 전체 전깃줄에서 구한 개수를 뺀다.

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

int n,a,b,tmp;
int dp[101];
vector<pair<int,int>> v;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end());
    dp[0]=1;
	for(int i=0;i<n;i++)
	{
		tmp=0;
		for(int j=0;j<i;j++)
		{
			if(v[j].second<v[i].second&&tmp<dp[j])
                tmp=dp[j];
		}
		dp[i]=tmp+1;
	}
	sort(dp,dp+n,greater<>());
	cout<<n-dp[0];
}

기쁜 소식

solved 골드 달성했다!