백준 2565번 전깃줄

🔒[문제 url]

https://www.acmicpc.net/problem/2565

🔑알고리즘

전깃줄이 엉키지 않기 위해서는, A의 번호가 오름차순 되어있고, B에 연결된 전깃줄의 위치 번호가 오름차순을 이루어야한다.
또한 최소한의 전깃줄을 잘라야하므로, B에 연결된 전깃줄의 위치 수열에서
가장 긴 증가하는 부분 수열을 찾고, 해당 수열에 속하지 않는 전깃줄을 자르면 된다.

• A의 번호를 기준으로 오름차순 정렬한 후, B에서 가장 긴 증가하는 부분 수열의 길이를 찾는다.
  • 가장 긴 증가하는 부분 수열이란?
    ex> { 1 , 3 , 2 , 5 , 4 , 6 } : { 1 , 3 , 5 , 6 }
    
    
• 가장 긴 증가하는 부분 수열의 길이는 어떻게 구하는가?
  • 수열에서 현재 위치의 값이 이전 지점의 값보다 클 때,
    증가하는 부분 수열의 길이는 1만큼 증가한다.
    따라서, 현재 지점에서 모든 이전 지점들을 순회하며 증가하는 부분 수열 길이의 최대값으로 현재 지점에서의 dp를 갱신한다.
  • dp[i] : 수열의 $i$번째 값을 포함한 부분 수열 중, 가장 긴 증가하는 부분 수열의 길이를 담는다.

🐾부분 코드

    // 가장 긴 증가하는 부분 수열을 찾고, 부분 수열에 해당하지 않는 전깃줄을 자른다.
    int longest = 1;
    for(int i = 1; i < n; i++)
    {
        int temp = 1;
        for(int j = 0; j < i; j++)
        {
        	// 현재 지점의 값이 이전 지점의 값보다 크다면
            if(wire[j].second < wire[i].second)
            {
            	// 증가하는 부분 수열의 길이를 1만큼 늘리고, 그중 최댓값으로 갱신한다
                temp = max(temp, dp[j] + 1);
            }
        }
        dp[i] = temp;
        longest = max(longest,dp[i]);
    }

<가장 긴 증가하는 부분 수열의 길이를 찾는 부분>
현재 지점에서 모든 이전 지점들을 순회하며, 증가하는 부분 수열의 값 중 가장 큰 값으로 dp를 갱신한다.

🪄전체 코드

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

int n;
vector<pair<int,int>> wire;
int dp[101];

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int a,b; cin >> a >> b;
        wire.push_back({a,b});
    }
}


void SOLVE()
{
    // B에 연결된 전깃줄이 오름차순이어야하므로, A를 기준으로 정렬해 제거할 전깃줄을 찾는다.
    sort(wire.begin(),wire.end());
    dp[0] = 1;

    // 가장 긴 증가하는 부분 수열을 찾고, 부분 수열에 해당하지 않는 전깃줄을 자른다.
    int longest = 1;
    for(int i = 1; i < n; i++)
    {
        int temp = 1;
        for(int j = 0; j < i; j++)
        {
        	// 현재 지점의 값이 이전 지점의 값보다 크다면
            if(wire[j].second < wire[i].second)
            {
            	// 증가하는 부분 수열의 길이를 1만큼 늘리고, 그중 최댓값으로 갱신한다
                temp = max(temp, dp[j] + 1);
            }
        }
        dp[i] = temp;
        longest = max(longest,dp[i]);
    }

    cout << n - longest;

}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

아이디어만 잡는다면.. 가장 긴 증가하는 부분 수열과 똑같은 문제였다.
근데 아이디어를 잡기가 어려운게 DP의 매력 아니겠어?!