[백준] 24505. blobhyperthink

https://www.acmicpc.net/problem/24505

문제요약

• 길이 11짜리 증가 수열의 개수 구하기

접근법

• LIS를 구하는 법을 생각해보면, 현재 위치보다 앞선 위치(왼쪽)에서 현재 값보다 작은 것들 중 가장 긴 것들에 연결하고, ......
• 변형해보면, 현재 위치보다 앞선 위치(왼쪽)에서 현재 값보다 작은 것들 중 길이가 10인 것들을 합하면 11인 것들을 구할 수 있음. 이를 모든 위치에 대해 합함
• 길이가 10은? 현재 위치에서........길이가 9인것들
• 반복 => 길이가 1은 기본이므로, 2부터 반복 가능
• 각 회차(k회차)에는 정렬 + 구간트리를 이용해서 값을 구해나감
  • 값이 작으면서 오른쪽에 있는 것부터 처리
  • 구간트리에 셋팅 된 것들 중 현재보다 왼쪽에 있는 것들의 합을 구함 => LIS 구하는 그 방법
  • 기존에 갖고 있는 값은 k - 1길이에 대한 값이므로 구간트리에 셋팅
  • 새로 구한 값은 k 길이에 대한 값이므로 간직
  • k를 2부터 11까지 반복
  • ${O(n * log(n) * 11)}$ 상수를 감안해도 적절함

추가 생각

• LIS 구하는 방법을 응용해도 되지 않을까? lower_bound()??