일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- DP
- 이진탐색
- 이분탐색
- 펜윅트리
- 세그먼트트리
- 수학
- LazyPropagation
- 크루스칼
- 백준
- 이분매칭
- MST
- 위상정렬
- dfs
- DisjointSet
- boj
- 구현
- 비트마스크
- 브루트포스
- lis
- 투포인터
- 정렬
- 플로이드와샬
- 좌표압축
- 그리디
- 에라토스테네스의 체
- lca
- 다익스트라
- 누적합
- 삼분탐색
- BFS
Archives
- Today
- Total
lastknight00
[백준] 증가 수열의 갯수(17409) 본문
문제 링크 : [백준] 증가 수열의 갯수(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. Di로 끝나는 증가하는 부분 수열은 Di-1까지의 원소 중, Di보다 작은 원소의 뒤에 붙일 수 있습니다.
예시)
i=1일 때, 가능한 부분 수열 1
i=2일 때, 가능한 부분 수열은 2보다 작은 1에 붙일 수 있습니다.
i=3일 때, 가능한 부분 수열은 3보다 작은 (1,2)에붙일 수 있습니다.
1-2. 위 내용을 적용하여, 각 원소보다 작은 수의 갯수를 조회하는데, 세그먼트 트리를 이용합니다.(Di보다 작은 부분합 조회, Di의 값을 1증가) - 길이가 k인 증가하는 부분 수열을 구하기 위해서는 길이가 k-1인 부분 수열에 마지막 원소보다 큰 원소를 붙이면 됩니다.
- 두 성질을 이용하여, i번째 원소에 대해, i번째 원소보다 앞선 원소들을 대상으로 i번째 원소를 덧붙여 만들 수 있는 증가하는 부분 수열의 길이들을 카운팅합니다.
- 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