cpp, 이분 탐색
두 전깃줄 (A1,B1), (A2,B2)에 대해 만약 A1이 A2보다 작고, B1이 B2보다 작다면 두 선은 교차하지 않는다.
여기서 잠시 최장 증가 수열의 개념에 대해 알아보자.
정수 i , j에 대해 i < j이면 s[i] < s[j]이다.
여기서 i 를 A전봇대의 번호, s[i]를 B전봇대의 번호로 생각하면, 해당 문제는 A전봇대의 전깃줄들을 오름차순으로 탐색할 때, B의 값이 증가하는 형태를 띄는 순열의 최대값을 구하는 문제라는것을 알 수 있다.

Copyright © 2024 Hyunghoon Kim