[백준/Baekjoon] 2565 전깃줄 C++ :: Dynamic Programming

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

2565번: 전깃줄

---

1. Logic

- 기본적인 LIS문제이다. 이 문제가 LIS인 이유는 전깃줄이 교차하지 않아야한다는 것은 이전 전깃줄의 번호가 다음 전깃줄의 번호보다 커지면 안되고 항상 작은 번호여야하기 때문에 증가하는 부분수열이 될 수 밖에 없다.

다른 LIS문제와 다른점은 단지 입력 값을 pair로 받아 준 다음 A를 기준으로 오름차순 정리해주고 B를 기준으로 LIS를 찾아주면 된다.

 

공부겸 시간복잡도가 O(nlogn)인 이분탐색을 활용한 LIS를 구하는 방식으로도 풀어놓았다. 코드는 dp와 이분탐색 둘다 올려놓았다.

---

2. Code

Dynamic programming을 활용한 LIS

#include<bits/stdc++.h>

using namespace std;

int n;
vector<pair<int, int>> input;
int dp[501][501];

int solve(int prevSelect, int idx) {
    if(idx == n) return 0;
    int &ret = dp[prevSelect][idx];
    if(ret != -1) return ret;

    ret = 0;

    for(int i = idx; i < n; i++) {
        if(prevSelect < input[i].second) {
            ret = max(ret, solve(input[i].second, i + 1) + 1);
        }
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;

        input.push_back({a, b});
    }

    sort(input.begin(), input.end());

    cout << n - solve(0, 0);
}

 

이분탐색을 활용한 LIS풀이(O(NlogN))

#include<bits/stdc++.h>

using namespace std;

int n;
vector<pair<int, int>> input;
vector<int> lis;
int cnt = 0;

int binarySearch(int key) {
    int left = 0;
    int right = lis.size() - 1;
    int mid;

    while(left < right) {
        mid = (left + right) / 2;

        if(key > lis[mid]) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }

    return right;
}

void solve() {
    for(int i = 0; i < n; i++) {
        if(lis.empty() || lis.back() < input[i].second) {
            lis.push_back(input[i].second);
            cnt++;
        }
        else {
            int idx = binarySearch(input[i].second);
            //int idx = lower_bound(lis.begin(), lis.end(), input[i].second) - lis.begin();
            lis[idx] = input[i].second;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;

        input.push_back({a, b});
    }

    sort(input.begin(), input.end());

    solve();

    cout << n - cnt << "\n";
}

 

---

3. Feedback

어제 공부한 이분탐색으로도 풀어봤는데 이분탐색의 종료조건을 헷갈려서 시간이 조금 걸렸다 5분정도? 이분탐색을 조금 더 디테일 하게 공부할 수 있는 기회가 생겨서 다행이다. 확실히 모르는데 그냥 넘어갈 뻔 했네

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐