[백준/BOJ] 17411 가장 긴 증가하는 부분 수열 6 (c++)

[백준/BOJ] 17411 가장 긴 증가하는 부분 수열 6 (c++)

17411번: 가장 긴 증가하는 부분 수열 6

14. Longest Increasing Subsequence (LIS, c++)

14. Longest Increasing Subsequence (LIS, c++)

---

이번 문제는 LIS의 길이와 구성요소를 하나만 출력하는 것이 아니라, LIS의 길이와 갯수를 찾아야 합니다.

 

2025.03.04 - [문제풀이] - [백준/BOJ] 14003 가장 긴 증가하는 부분 수열 5 (c++)

[백준/BOJ] 14003 가장 긴 증가하는 부분 수열 5 (c++)

 

위 문제와 동일하게 d에는 LIS의 k번째 위치할 수 있는 가장 작은 숫자를 저장하고 p에는 i번째 숫자가 LIS의 k번째에 위치할 수 있었다는 정보를 저장합니다. a에는 실제 수열의 숫자들이 저장되어 있습니다.

 

p에 담긴 정보를 이용하면 LIS의 갯수를 세어볼 수 있습니다.

 

i번째 숫자까지 만들 수 있는 LIS의 갯수는 모든 i-1번째 숫자에 대해서

 

a[i] > a[i-1] 이면서 p[i] = p[i-1]+1 인 수들의 경우의 수의 합으로 계산해볼 수 있습니다.

 

그러나 이렇게 모든 i-1 번째까지 탐색을 하게되면 시간초과가 발생을 할 것입니다.

 

어딘가 정렬이 되어있어야 탐색을 빠르게 할 수 있을텐데,

 

반대로 생각을 해보면 LIS를 구하는 과정에서 더 큰 숫자가 나오면 LIS의 length가 늘어나기 때문에 p의 값인 k가 같은 숫자들은 역방향으로 탐색할 시 항상 오름차순으로 나오게 됩니다.

 

{ 2, 1, 5, 0, 7, 4, 8, 3 }  이라는 수열에 대해 계산해보면 아래와 같습니다.

 

P 가 0인 경우 -> { 0, 1, 2 }

P 가 1인 경우 -> { 4, 5 }

	P	D
2	0	{ 2 }
1	0	{ 1 }
5	1	{ 1, 5 }
0	0	{ 0, 5 }
7	2	{ 0, 5, 7 }
4	1	{ 0, 4, 7 }
8	3	{ 0, 4, 7, 8 }
3	1	{ 0, 3, 7, 8 }

 

그러므로 정리해보면 P[i] = LIS의 길이인 숫자들은 항상 1개 만들 수 있습니다.

 

P[i]가 LIS길이보다 작은 숫자들은, P[i]+1 을 가진 수들 z에 대해서

1) z는 i보다 나중에 등장해야 하고

2) a[i] < a[z] 인

3) 모든 z들의 경우의 수의 합으로 계산할 수 있습니다.

 

1) z는 i보다 나중에 등장해야 한다. 는 뒤에서 부터 순차적으로 탐색을 하면 해결이 됩니다.

 

2) a[i] < a[z] 는 P의 값인 k가 같은 숫자들은 오름차순으로 등장하기 때문에 k에 따라 다른 vector를 사용하면 k+1의 vector에 upper_bound를 검색하는 것으로 O(logN)에 구할 수 있습니다.

 

3) 모든 z들의 경우의 수의 합은 k에 따라 다른 vector에 prefix sum을 구해두면 원하는 범위에 대한 합을 O(1)에 구할 수 있습니다. 편의를 위해 모든 psum vector에는 0을 미리 추가해 두는 것이 좋습니다.

 

반대로 탐색시 값이 구해지는 과정은 다음과 같습니다.

	r	upper_bound	psum (전체 합 - upper_bound index)  = upper_bound 숫자까지의 경우의 수
3	r[1] = { 3 }	r[2]에 수행 = 0	psum[2]에 대해 수행 (0-0)=0, psum[1] = { 0, 0 }
8	r[3] = { 8 }	-	psum[3] = { 0, 1 }
4	r[1] = { 3, 4 }	r[2]에 수행 = 0	psum[2]에 대해 수행 (0-0)=0, psum[1] = { 0, 0, 0 }
7	r[2] = { 7 }	r[3]에 수행 = 0	psum[3]에 대해 수행 (1-0)=1, psum[2] = { 0, 1 }
0	r[0] = { 0 }	r[1]에 수행 = 0	psum[1]에 대해 수행 (0-0)=0, psum[0] = { 0, 0 }
5	r[1] = { 3, 4, 5 }	r[2]에 수행 = 0	psum[2]에 대해 수행 (1-0)=0 psum[1] = { 0, 0, 0, 1 }
1	r[0] = { 0, 1 }	r[1]에 수행 = 0	psum[1]에 대해 수행 (1-0)=0 psum[0] = { 0, 0, 1 }
2	r[1] = { 0, 1, 2 }	r[1]에 수행 = 0	psum[1]에 대해 수행 (1-0)=0 psum[0] = { 0, 0, 1, 2 }

 

이와 같은 방식으로 LIS의 총 길이는 4이며, 길이 4인 LIS는 2개 존재함을 찾아낼 수 있습니다.

 

이 문제에서는 psum간의 -연산이 있으므로 MOD 연산 사용시 역전되는 것을 주의해야합니다. 따라서 long long을 사용하고 결과에 영향을 주지 않는 선에서 MOD연산을 해주어야 합니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
#define MOD 1000000007
int N, x;
vector<int> a, d, p;
vector<vector<int>> r(1000000);
vector<vector<long long>> psum(1000000);

int solve() {
    REP(i, 0, N) {
        int index = lower_bound(d.begin(), d.end(), a[i])-d.begin();
        if (index >= d.size()) d.push_back(a[i]);
        else d[index] = a[i];
        p.push_back(index);
    }
    REP(i, 0, d.size()) {
        psum[i].push_back(0);
    }
    REP(i, 0, N) {
        int len = p[N-i-1];
        if (len == d.size()-1) {
            psum[len].push_back(psum[len].back()+1);
        } else {
            int index = upper_bound(r[len+1].begin(), r[len+1].end(), a[N-i-1])-r[len+1].begin();
            long long cnt = (psum[len+1].back()-psum[len+1][index])%MOD;
            psum[len].push_back(psum[len].back()+cnt);
        }
        r[len].push_back(a[N-i-1]);
    }

    cout << d.size() << " " << (psum[0].back()%MOD);
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    REP(i, 0, N) {
        cin >> x;
        a.push_back(x);
    }
    solve();
    return 0;
}