22880 봉화대

 

이전에 잘랐던 내용 포함해서 계산해야 하기 때문에  DP를 사용해서 풀었다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

void printVector(vector<i64> &v) {
    for (int i = 0; i < v.size(); i++)
        printf("%lld ", v[i]);
    printf("\n");
}

int main() {
    i64 n;
    scanf("%lld", &n);
    
    vector<i64> v(n);
    for (i64 i = 0; i < n; i++)
        scanf("%lld", &v[i]);
    
    // 가장 높은 높이 구하기
    vector<i64> highestIdx(n);
    highestIdx[0] = 0;
    for (i64 i = 1; i < n; i++){
        if (v[i] > v[highestIdx[i - 1]])
            highestIdx[i] = i;
        else
            highestIdx[i] = highestIdx[i - 1];
    }
    
    
    
    // 연속된 수의 개수 구하기
    vector<i64> continuous(n);
    continuous[0] = 1;
    for (i64 i = 1; i < n; i++){
        if (highestIdx[i] == highestIdx[i - 1])
            continuous[i] = continuous[i - 1] + 1;
        else
            continuous[i] = 1;
    }
    
    
    
    vector<i64> dp(n);
    dp[0] = 1;
    for (i64 i = 1; i < n; i++) {
        //가장 높은 인덱스가 아닐 때
        if (highestIdx[i] != i) {
            dp[i] = dp[i-1];
            continue;
        }
        
        //가장 높은 인덱스를 만났을 때
        dp[i] =  (dp[highestIdx[i - 1]] * continuous[i - 1] + dp[highestIdx[i - 1]]) % 1000000007;
    }
    
    printf("%lld\n", dp[n-1]);
    
    return 0;
}