승진 사슬
골드 III의견: 0
신입 사원 \(N\)명을 평가했다. 사원 \(i\)는 업무 능력 \(a_i\)와 성장 잠재력 \(b_i\)를 가진다. 인사팀은 승진 사슬을 만들려 한다. 승진 사슬이란 사원들을 골라 일렬로 세운 것으로, 사슬에서 앞에 선 사원보다 뒤에 선 사원이 업무 능력과 성장 잠재력이 둘 다 엄격히 큰 것을 말한다.
즉, 사슬에 속한 사원들을 적절히 정렬하면 \(a\) 값도 엄격히 증가하고 \(b\) 값도 엄격히 증가해야 한다. 만들 수 있는 가장 긴 승진 사슬의 길이를 구하여라.
\(1 \le N \le 200{,}000\), \(1 \le a_i, b_i \le 10^9\). 같은 \((a_i, b_i)\) 쌍이 여러 번 나올 수 있다.
첫째 줄에 사원 수 \(N\)이 주어진다. 이어 \(N\)개의 줄에 각각 두 정수 \(a_i\), \(b_i\)가 주어진다.
가장 긴 승진 사슬의 길이를 한 줄에 출력한다.
5
1 1
2 3
2 2
3 4
3 1
3\((1,1)\to(2,2)\to(3,4)\) 는 두 값 모두 엄격히 증가하는 길이 3의 사슬이다. 더 긴 사슬은 없다.
3
5 5
5 9
5 1
1세 사원의 \(a\) 값이 모두 5로 같아서 어느 둘도 \(a\)가 엄격히 증가할 수 없다. 따라서 한 명만 고를 수 있어 답은 1이다.
골드 IIriseoj 작성
출처 Original
평가 및 의견
승진 사슬
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
승진 사슬