[ 백준 2565 ] 전깃줄 (C++) - DP

---

🔗 문제 링크

2565번: 전깃줄

---

💡 문제 풀이 및 해석

1. N <= 500 이므로 브루트포스 혹은 탐색으로는 풀 수 없는 문제이다.
2. 설명하기 어렵지만, 증가하는 부분 수열 느낌의 문제로 DP를 활용한 문제임을 알 수 있다.
3. 왼쪽 건물을 기준으로 정렬을 해서 순서대로 dp를 이어간다.
4. 정렬된 순서 기준으로, 나보다 먼저 전깃줄을 설치된 오른쪽 번호가 현재 내 번호보다 작으면 비교를할 수 있다.
5. 오른쪽 건물 기준으로, 현재 검사 중인 전깃줄보다 먼저 설치된 전깃줄이 더 위에 있다면, 그 위치의 dp를 검사한다.
6. 5번을 끝까지 반복하면 안겹치는 최대의 전깃줄 개수가 나온다. 따라서 전체에서 최대 전깃줄 개수를 빼주면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N;
int* dp;
vector<pair<int,int>> building;

void input() {
    cin >> N;
    dp = new int[N + 1];
    building.push_back({ -1,-1 });
    for (int i = 1; i <= N; i++) {
        int left, right; cin >> left >> right;
        building.push_back({ left,right });
        dp[i] = 1;
    }
    sort(building.begin(), building.end());
}

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

int main() {

    input();
    sol();

    return 0;
}

---

🤔 문제 후기

문제 풀이 및 해석에서 뭔가 중구난방으로 써놓은 것 처럼, 문제를 풀 때도 느낌으로 이렇게 하면 될 것이다~ 라고 생각하고 푼 것이지 정확하게 이렇게 하면 맞아! 하고 푼 문제는 아니다. 그렇게 풀다보니 로직을 구현할 때도 처음에는 for문을 이중으로 안하고 하나의 반복문 안에 다 처리할 수 있지 않을까? 하면서 시간도 많이 낭비했다. 결과적으로 처음에 생각한대로 풀었더니 맞긴 했는데, 정확하게 알아서 풀었다고 보기는 어려운 문제인 것 같다.