BOJ 8311 - Variable Subsequences

문제 링크 : https://www.acmicpc.net/problem/8311 

문제 풀이

 문제를 읽으면 상태가 (1~i 까지 중에서, 부분 배열의 마지막 숫자) 와 같은 식으로 나오기 때문에 DP를 떠올리게 된다. 하지만, $A_i$ 는 단지 수 하나이기 때문에 dp[i-1] 에서 dp[i] 로 넘어갈때 dp[i][$A_i$] 만 바뀌게 되고, 따라서 2차원 DP를 할 필요 없이 그냥 부분 배열의 마지막 숫자만 들고 있으면 된다. 

 DP[$A_i$]에 업데이트 할 값은 $ \sum_{j=1,j\neq A_i}^{N} DP[j] $ 이기 때문에 DP의 모든 칸의 합을 변수로 들고 있으면서  DP[$A_i$] 값만 빼주고 업데이트 하면 된다. 시간 복잡도는 $O(N)$

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll val,xx,yy;
};
 
vector<ll> x;
ll n,m;
ll mod=1000000007;
string s;
string t;
ll arr[1010101];
vector<ll> v[1010101];
ll dp[1010101];
ll all=1;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,a,b,c,d,e,f;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a;        
        ll x=all-dp[a];
        all+=x;
        dp[a]+=x;
        all%=mod;
    }
    all--;
    all+=mod;
    cout<<all%mod;
}