[Softeer/소프티어][level3] 징검다리 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=390&sw_prbl_sbms_sn=18384

Softeer

 

 

[난이도] level3
[유형] DP

[풀이]
LIS(Longest Increasing Subsequence) 다이나믹 프로그래밍 문제입니다.
돌계단의 높이가 높아지는 순서로 선택하고, 그 개수를 최대로 해야하기 때문입니다.
N 제한 3000이기 때문에 O(N^2) 시간복잡도 풀이로 해결이 가능합니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,a[3001],dp[3001];
int sol(int n){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    for(int i=n+1;i<=N;i++)
        if(a[n]<a[i]) ret=max(ret,1+sol(i));
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0));
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/징검다리.cpp