티스토리 뷰
증가하는 부분 수열
(http://boj.kr/13555)
앞의 원소부터 차례대로 원소의 값을 인덱스로 해서 배열에 저장해두면,
현재 원소의 값보다 작은 인덱스에 저장된 것들은 현재 원소보다 앞에 있고 작은 것들이라는 의미이다.
이 방법으로 개수도 구할 수 있다.
Dij를 i번째 항으로 끝나는 길이가 j인 증가하는 부분 수열의 개수라고 할 때,
앞의 방법대로 구할 수 있다.
인덱스가 작은 항부터 넣을 때, 길이가 j인 수열을 만들려면 자신의 값보다 앞에 있는 것들 중 길이가 j−1인 것들에 현재 원소를 붙여야 한다.
즉, 자신의 값보다 앞에 있는 것들의 길이가 j−1인 수열 개수의 합이다.
Dij=Dkj−1(k=1,2,3,⋯,i−1이고 arr[k]<arr[i])
이 합을 구할 때 O(N)으로 하면 시간초과가 나기 때문에 O(logN)으로 구할 수 있는 세그먼트 트리나 펜윅 트리 등을 사용해야 한다.
'문제' 카테고리의 다른 글
BOJ 2499 의좋은 형제 (1) | 2018.07.23 |
---|---|
BOJ 10713 기차 여행 (0) | 2018.07.23 |
BOJ 10160 암호 (0) | 2018.05.13 |
BOJ 2482 색상환 (0) | 2018.05.06 |
BOJ 14864 줄서기 (0) | 2018.04.10 |