BOJ 11053번: 가장 긴 증가하는 부분 수열

문제

문제 바로가기> BOJ 11053번: 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

 

풀이

DP와 이중 for문을 이용해 "현재 수를 마지막으로 하는 가장 긴 증가하는 부분 수열"의 길이를 저장해주었다.

이렇게 저장해두면, 답은 dp 배열 중 가장 큰 값이 되고, 이를 반복문을 돌 때 함께 업데이트 해주면 된다!

 

#include<iostream>
#define MAX 1001
using namespace std;

int N;
int A[MAX], dp[MAX]; // dp[i] : i번째 값을 마지막으로 하는 가장 긴 증가하는 부분 수열

void input(){
    cin >> N;
    for(int i=0; i<N; i++) cin >> A[i];
}

void solution(){  
    int ans = 0;
    for(int i=0; i<N; i++){
        dp[i] = 1;
        for(int j=0; j<i; j++) {
            if(A[j] < A[i]) dp[i] = max(dp[i], dp[j]+1);
        }
        ans = max(ans, dp[i]);
    } cout << ans;
}

int main(){
    freopen("input.txt", "r", stdin);
    input();
    solution();
}