백준 2550 - 전구 (C++)

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

제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 10,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 가장 긴 증가하는 부분 수열 O(NlogN) 풀이 그림만 봐도 알겠지만, 기본적인 lis 역추적 문제이다. $N$의 범위에 따라 $O(NlogN)$ 솔루션이 강제되지 않기 때문에, 굳이 이분 탐색을 이용하지 않아도 널널해 보인다.

전체 코드 12345678910111213141516171819202122232425262728#include#define N 10001using namespace std; vect.....