원

https://www.acmicpc.net/problem/18892 18892번: 가장 긴 증가하는 부분 수열 ks N개의 정수로 이루어진 수열 A1, A2, ..., AN에서, 가장 긴 증가하는 부분 수열(LIS)의 길이를 L이라고 하자. LIS는 하나 또는 그 이상 있을 수 있다. 모든 LIS를 사전 순으로 정렬했을 때, K번째 오는 수 www.acmicpc.net 문제 N개의 정수로 이루어진 수열 A1, A2, ..., AN에서, 가장 긴 증가하는 부분 수열(LIS)의 길이를 L이라고 하자. LIS는 하나 또는 그 이상 있을 수 있다. 모든 LIS를 사전 순으로 정렬했을 때, K번째 오는 수열을 구해보자. 두 LIS Ai1, Ai2, ..., AiL와 Aj1, Aj2, ..., AjL이 있을 때, ..

https://www.acmicpc.net/problem/12014 12014번: 주식 입력 파일에는 여러 테스트 메이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 www.acmicpc.net N일 동안 주식을 K일 동안 살건데, K일 동안의 주식 가격은 모두 상승세이어야한다. 가장 긴 증가하는 부분 수열을 구했을 때 길이가 K를 만족하면 위 조건을 만족하고, K일 간의 가장 긴 증가하는 부분 수열을 구하지 못한다면 K일 동안 주식을 살 수 없다. 즉, 가장 긴 증가하는 부분 수열 알고리즘을 이용하여 길이만 만족하는지 확인하면 되는 문제 LIS알고리즘은 이분 탐색을 응용한 O(n..