[백준/BOJ] 2565번 : 전깃줄 (동적 프로그래밍(DP), Gold V)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2565번 : '전깃줄' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold V에 해당하며, 문제를 풀이하기 위해 동적 프로그래밍(DP)에 대한 이해가 필요합니다.

 

 

2565번 : 전깃줄

 

전깃줄이 서로 교차하지 않도록 제거해야 하는 최소 전깃줄의 개수를 구하는 문제입니다.

A에 대해 증가하는 순으로 정렬을 해준 뒤, B에서 가장 긴 증가하는 부분 수열의 길이를 찾아주어 전체 전깃줄의 수에서 빼주면 구할 수 있음을 쉽게 알 수 있습니다.

 

[백준/BOJ] 11054번 : 가장 긴 바이토닉 부분 수열 (+ 11053번, 11054번 풀이 포함)

↑ 가장 긴 증가하는 부분 수열 문제에 대한 간단한 풀이는 위의 포스트를 참조하면 도움이 될 것입니다.

그럼 이를 활용하여 풀이를 해보겠습니다.

 

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;
    vector<pair<int, int>> arr; arr.resize(N);
    for(int i=0; i<N; i++)
        cin >> arr[i].first >> arr[i].second;
    sort(arr.begin(), arr.end());
    int dp[1000]; fill(dp, dp+1000, 1);

    int LIS = 1;
    for(int i=0; i<N; i++) {
        for(int j=0; j<i; j++)
            if(arr[i].second > arr[j].second) dp[i] = max(dp[i], dp[j]+1);
        LIS = max(LIS, dp[i]);
    }
    cout << N - LIS;
}

 

먼저 arr을 pair로 선언해준 뒤 A와 B의 위치를 각각 입력받아준 뒤, A에 대해서 정렬을 먼저 해줍니다.

이후 최장 증가 부분 수열(LIS)의 길이를 구하는 알고리즘은 어렵지 않은데, i와 j에 대해서 이중 for문을 돌면서 j번째 수보다 i번째 수가 더 큰 경우 dp[i]와 dp[j] + 1을 비교하여 더 큰 쪽을 LIS의 값으로 지정해주면 됩니다.

마지막에는 LIS의 길이가 아닌 제거해야하는 최소 전깃줄의 수를 구해야하므로 전체 전깃줄의 수에서 LIS의 값을 빼주면 됩니다.

 

 

 

풀이 코드를 제출하면 위의 기록으로 정답 처리를 받을 수 있습니다.