BOJ 2352 : 반도체 설계

풀이 요약

DP (LIS) 를 활용한 문제

풀이 상세

1. 두 포트가 꼬이거나 겹치지 않는 경우는 연결되는 끝 포트의 인덱스가 지속적으로 커지면 된다.
2. 즉 부분 수열이 계속해서 커져나가는 것 가운데, 최대로 커지는 수열의 갯수를 구하면 된다.
3. 나의 경우, lowerbound를 활용하여 현재 증가하거나 동일한 인덱스의 값을 업데이트 하며 남은 최종 리스트 갯수를 반환하는 방식으로 구했다.

배운점

• lowerbound, upperbound 에 대해 다시 한번 공부했다. lowerbound 란 중복되어 일치한 인덱스 가운데 가장 작은 인덱스를 반환하며, upperbound의 경우 일치한 인덱스의 다음 인덱스를 반환한다.
• 코테를 보면, 당연히 그래프 관련 완탐 문제가 많이 나온다고 하는데… 나는 아닌 거 같다. 특히 어려운 문제는 그리디나 map 관련 문제, string 관련 문제가 많이 나온듯 하다. 이분탐색도 그리디 와 함께 쓰이거나, 종종 예외 상황을 지켜야만 해결되는 문제가 많다. 요런 문제들 위주로 풀어봐야겠다.

#include <iostream>
#include <vector>

using namespace std;
int N, num;
vector<int> v;

int lowerBound(int curr) {
    int l = 0;
    int r = v.size();
    while (l < r) v[(l + r) / 2] >= curr ? r = (l + r) / 2 : l = (l + r) / 2 + 1;
    return r;
}

void input() {
    cin >> N >> num;
    v.push_back(num);
    for (int i = 1; i < N; i++) {
        cin >> num;
        if (v.back() < num) v.push_back(num);
        else v[lowerBound(num)] = num;
    }
}

void output() {
    cout << v.size();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    output();
}