[백준/G2] 가장 긴 증가하는 부분 수열 3

12738번: 가장 긴 증가하는 부분 수열 3 12738번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 가장 긴 증가하는 부분 수열 3 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 3 초 512 MB 8776 4932 4013 62.401% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 , 20 , 10, 30 , 20, 50 } 이고, 길이는 4이다.

입력 첫째 줄에 수열 ... www.acmicpc.net LIS의 O(NlgN) 풀이로는 이분탐색 풀이가 더 잘 알려져 있지만 나는 세그먼트 트리를 이용하여 해결했다. j=0부터 j=arr[i] - 1까지 dp[j]의 값의 최댓값을 구한 후 1을 더해주면 dp[i]를 구할 수 있다. 이 때, 세그먼트 트리를 이용하면 최댓값을 빠르게 구할...