lastknight00

[백준] 증가 수열의 갯수(17409) 본문

PS

[백준] 증가 수열의 갯수(17409)

lastknight00 2020. 5. 26. 19:50

문제 링크 : [백준] 증가 수열의 갯수(17409)

문제 설명

n개의 원소를 가지는 수열이 주어졌을 때, 증가하는 수열의 길이가 k인 부분 수열이 몇개가 있는지 구하여라.

입력

n(배열의 갯수, 1<=n<=100,000)
k(증가하는 수열의 길이,1<=k<=10)
Di(n개의 수열의 값, 1<=Di<=n, 서로 다른 수)

5 1
1 2 3 5 4

출력

길이가 k인 증가하는 부분 수열의 갯수

5

카테고리

#segment tree, #fenwick tree

시간 복잡도 상한

O(knlogn) 까지 가능합니다.

해결 방법

  1. 증가하는 부분 수열의 길이는 누적합을 통하여 구할 수 있습니다.
    1-1. Di로 끝나는 증가하는 부분 수열은 Di-1까지의 원소 중, Di보다 작은 원소의 뒤에 붙일 수 있습니다.
    예시)
    i=1일 때, 가능한 부분 수열 1
    i=2일 때, 가능한 부분 수열은 2보다 작은 1에 붙일 수 있습니다.
    i=3일 때, 가능한 부분 수열은 3보다 작은 (1,2)에붙일 수 있습니다.
    1-2. 위 내용을 적용하여, 각 원소보다 작은 수의 갯수를 조회하는데, 세그먼트 트리를 이용합니다.(Di보다 작은 부분합 조회, Di의 값을 1증가)
  2. 길이가 k인 증가하는 부분 수열을 구하기 위해서는 길이가 k-1인 부분 수열에 마지막 원소보다 큰 원소를 붙이면 됩니다.
  3. 두 성질을 이용하여, i번째 원소에 대해, i번째 원소보다 앞선 원소들을 대상으로 i번째 원소를 덧붙여 만들 수 있는 증가하는 부분 수열의 길이들을 카운팅합니다.
  4. 3에서 카운팅한 값들 중 길이가 k인 경우들을 모두 더하여 출력합니다.

시간복잡도

O(knlogn)

코드

#include<iostream>
using namespace std;
typedef long long L;
int n,m,d,i,j;
L t[11][100002],s;
L q(int p,int k){
    L s=0;
    while(p)s=(s+t[k][p])%1000000007,p-=p&-p;
    return s;
}
void u(int p,int k,L v){
    while(p<=n+1)t[k][p]=(t[k][p]+v)%1000000007,p+=p&-p;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    u(1,0,1);
    for(i=0;i<n;i++){
        cin>>d;d++;
        for(j=1;j<=m;j++)u(d,j,q(d-1,j-1));
    }
    cout<<q(n+1,m);
}

'PS' 카테고리의 다른 글

[백준] 틱택토(7682)  (0) 2020.05.26
[백준] 징검다리 달리기2(1810)  (0) 2020.05.26
[백준] 인경호의 징검다리(11583)  (0) 2020.05.26
[백준] 커플 만들기(1727)  (0) 2020.05.26
[백준] 로봇 프로젝트(3649)  (0) 2020.05.26
Comments