백준 17409 - 증가 수열의 개수

증가 수열의 개수

풀이

왼쪽부터 수열 A를 받아 dp에 저장한다고 하자.
dp[n][k] := n을 최대 수로 갖는 길이가 k인 증가하는 부분 수열의 갯수 이라 하자.
현재 수를 n+1이라 할 때, dp[n+1][k+1]은 dp[1~n][k]의 모든 합을 더한 값이 될 것이다.
왜냐하면 dp[1~n][k]은 현재 수보다 왼쪽에 있으면서 끝 수가 n+1보다 작은 증가하는 부분수열의 갯수들이기 떄문이다.

위 합은 세그먼트 트리나 펜윅 트리로 저장하여 그 값을 저장하면 될 것이다.
정답은 dp[1~N][K]의 합이 될 것이다.

코드

코드1 - 세그먼트 트리

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, a, b) for(ll i=(a); i<(b); i++)
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define Bor(i, a, b) for(ll i=(a); i>(b); i--)
#define BOR(i, a, b) for(ll i=(a); i>=(b); i--)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

const ll mod = 1e9+7;

class Segment {
public:
    vector<ll> tree; //tree[node] := a[start ~ end] 의 합

    Segment() {}
    Segment(int size) {
        this->resize(size);
    }
    void resize(int size) {
        size = (int) floor(log2(size)) + 2;
        size = pow(2, size);
        tree.resize(size, 0);
    }
    ll sum(int node, int start, int end, int left, int right) {
        if(right < start || end < left) return 0;
        if(left <= start && end <= right) return tree[node];
        return (sum(node * 2, start, (start + end) / 2, left, right) +
                sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right)) % mod;
    }
    void update(int node, int start, int end, int index, ll value) {
        if(index < start || end < index) return;
        if(start == end) tree[node] = value % mod;
        else {
            update(node * 2, start, (start + end) / 2, index, value);
            update(node * 2 + 1, (start + end) / 2 + 1, end, index, value);
            tree[node] = (tree[2*node] + tree[2*node+1]) % mod;
        }
    }
};

void solve() {
    int n, k; cin >> n >> k;
    Segment tree[11];
    FOR(i,1,10) tree[i].resize(n);

    FOR(i,1,n) {
        int a; cin >> a;
        tree[1].update(1,1,n,a,1);
        for(int kk=2; kk<=k; kk++) {
            ll res = tree[kk-1].sum(1,1,n,1,a-1);
            tree[kk].update(1,1,n,a,res);
        }
    }

    cout << tree[k].sum(1,1,n,1,n) << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
//    cin >> TC;
    FOR(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}

코드2 - 펜윅트리

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, a, b) for(ll i=(a); i<(b); i++)
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define Bor(i, a, b) for(ll i=(a); i>(b); i--)
#define BOR(i, a, b) for(ll i=(a); i>=(b); i--)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

const ll mod = 1e9+7;

class FenwickTree {
private:
    int size;
    vector<ll> tree;

public:
    FenwickTree(int size) : size(size) {
        tree.assign(size + 1, 0);
    }

    void update(int idx, ll delta) {
        while (idx <= size) {
            tree[idx] = (tree[idx] + delta) % mod;
            idx += idx & -idx;
        }
    }

    ll query(int idx) {
        ll sum = 0;
        while (idx > 0) {
            sum = (sum + tree[idx]) % mod;
            idx -= idx & -idx;
        }
        return sum;
    }
};

void solve() {
    int n, k; cin >> n >> k;
    vector<FenwickTree> tree(k+1, FenwickTree(n));

    FOR(i,1,n) {
        int a; cin >> a;
        tree[1].update(a,1);
        for(int kk=2; kk<=k; kk++) {
            ll res = tree[kk-1].query(a-1);
            tree[kk].update(a,res);
        }
    }

    cout << tree[k].query(n) << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
//    cin >> TC;
    FOR(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}