[BOJ 17409 // C++] 증가 수열의 개수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17409번 문제인 증가 수열의 개수이다.
문제는 아래 링크를 확인하자.

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

17409번: 증가 수열의 개수

길이가 K인 증가수열의 개수를 세야 하는 문제이다.

K의 범위가 10 이하로 적으므로, 단순히 K가 10 이하인 각 경우로 케이스를 나누어도 무방하다.

LIS를 세그먼트 트리를 이용하여 구하는 방법을 활용하면 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll seg[11][262145];

void update(int L, int R, int qI, ll qVal, int k) {
	int sI = 1;
	while (L < R) {
		seg[k][sI] += qVal;
		seg[k][sI] %= 1000000007;
		int mid = (L + R) / 2;
		if (qI <= mid) {
			R = mid;
			sI = sI * 2;
		}
		else {
			L = mid + 1;
			sI = sI * 2 + 1;
		}
	}
	seg[k][sI] += qVal;
	seg[k][sI] %= 1000000007;
}

ll rangesum(int L, int R, int qL, int qR, int sI, int k) {
	if (qR < L || R < qL) return 0;
	if (qL <= L && R <= qR) return seg[k][sI];
	return (rangesum(L, (L + R) / 2, qL, qR, sI * 2, k) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1, k))%1000000007;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K; cin >> N >> K;
	int NN = N;
	while (NN--) {
		int x; cin >> x;
		for (int k = 10; k > 1; k--) {
			ll cnt = rangesum(1, N, 1, x, 1, k - 1);
			update(1, N, x, cnt, k);
		}
		update(1, N, x, 1, 1);
	}

	cout << seg[K][1];
}