티스토리 뷰

문제

BOJ 13555 증가하는 부분 수열

klimmek55 2018. 7. 17. 00:52

증가하는 부분 수열
(http://boj.kr/13555)

앞의 원소부터 차례대로 원소의 값을 인덱스로 해서 배열에 저장해두면,
현재 원소의 값보다 작은 인덱스에 저장된 것들은 현재 원소보다 앞에 있고 작은 것들이라는 의미이다.
이 방법으로 개수도 구할 수 있다.

Diji번째 항으로 끝나는 길이가 j인 증가하는 부분 수열의 개수라고 할 때,
앞의 방법대로 구할 수 있다.

인덱스가 작은 항부터 넣을 때, 길이가 j인 수열을 만들려면 자신의 값보다 앞에 있는 것들 중 길이가 j1인 것들에 현재 원소를 붙여야 한다.
즉, 자신의 값보다 앞에 있는 것들의 길이가 j1인 수열 개수의 합이다.
Dij=Dkj1(k=1,2,3,,i1이고 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
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/04   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함