백준 2550 - 전구 (C++)

문제

• 문제 링크

  
   BOJ 2550 - 전구 
  

• 문제 요약

$N$개의 스위치 및 전구의 연결 정보가 주어진다.
이때 교차하지 않게 가장 많은 전구를 켤 수 있는 경우를 추적해보자.

• 제한

TL : $1$ sec, ML : $128$ MB




$1 ≤ N ≤ 10,000$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 가장 긴 증가하는 부분 수열 O(NlogN)

풀이

   그림만 봐도 알겠지만, 기본적인 lis 역추적 문제이다.

$N$의 범위에 따라 $O(NlogN)$ 솔루션이 강제되지 않기 때문에, 굳이 이분 탐색을 이용하지 않아도 널널해 보인다.

전체 코드

#include<bits/stdc++.h>
#define N 10001
using namespace std;
 
vector <int> V, an;
int n, a[N], b[N], c[N], dp[N];
 
int main()
{
    cin >> n;
    for (int i(1); i <= n; i++)
        scanf("%d", &a[i]), b[a[i]] = i;
    for (int i(1), j; i <= n; i++)
        cin >> j, c[i] = b[j];
    for (int i(1), j; i <= n; i++)
    {
        j = lower_bound(V.begin(), V.end(), c[i]) - V.begin();
        if (j == V.size()) V.push_back(c[i]);
        else V[j] = c[i];
        dp[i] = j;
    }
    for (int i(n), k(*max_element(dp, dp + n + 1)); i; i--)
        if (dp[i] == k)
            an.push_back(a[c[i]]), k--;
    sort(an.begin(), an.end());
    cout << an.size() << '\n';
    for (int& i : an) printf("%d ", i);
}

comment

끝