[4248번] 유사 증가 수열

문제 출처 :

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWK3hsd6FkIDFAWJ&categoryId=AWK3hsd6FkIDFAWJ&categoryType=CODE

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

2. Dynamic Programming

아래 주석에 더 자세히 달아두었다.

구현과 dp를 이용하면 쉽게 해결 할 수 있다.

소스 코드 : 

#include <iostream>
 
typedef long long ll;
 
ll arr[100004];
ll dp[100004];
 
int main() {
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
    
    for (int tc = 1; tc <= tCase; tc++) {
        int n, k;
        scanf("%d %d", &n, &k);
 
        for (int i = 0; i < n + 2; i++)
            arr[i] = dp[i] = 0;
        
        for (int i = 0; i < n; i++)
            scanf("%lld", &arr[i]);
 
        int youSa = -1;
        int s = 0;
        int ans = 0;
        for (int e = 0; e < n; e++) {
            /* 
                유사증가수열 포인트가 없으면서
                arr[e-1] > arr[e]일때
                10 20 30 40 50 3 일때 3은 유사증가수열 포인트
            */
            if (youSa == -1 && arr[e - 1] > arr[e])
                youSa = e;
 
            /*
                유사증가수열 포인트가 있으면서
                arr[e-1] > arr[e]일때
                10 20 30 1 20 30 2 일때 s를 이전 포인트(1)로 보내고
                유사증가수열 포인트를 2로 갱신
            */
            else if (youSa != -1 && arr[e - 1] > arr[e]) {
                s = youSa;
                youSa = e;
            }
            
            /*
                유사증가수열 포인트가 있으면서
                arr[e-1] <= arr[e]이고 arr[e-2] > arr[e]일때
                10 20 30 2 40 3 50일때
                s는 2로 보냄
            */
            else if (youSa != -1 && arr[e - 1] <= arr[e] && arr[e - 2] > arr[e])
                s = youSa;
            
            int l = e - s + 1;
            if (l - k + 1 > 0)
                dp[e] = (l - k + 1);
        }
        for (int i = 0; i < n; i++) 
            ans += dp[i];
 
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}