[백준/C++][가장 긴 증가하는 부분 수열(11053번)]

문제

https://www.acmicpc.net/problem/11053

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

이 문제는 나도 다른 사람의 풀이를 보고 알았다. 다이나믹 프로그래밍은 너무 어려운듯하다.

 

문제해결

1. 10,20,10,30,20,50 이 수열A로 있으면 맨 처음 인덱스인 10의 대한 dp[0] = 1(길이) dp[1] = 2 dp[2] = 1 이런식으로 한다.

2. 처음 인덱스부터 자기자신 전까지 탐색를 한다.

3. 만약 자기자신보다 작은 숫자이면 현재자신의 dp의 값과 작은 숫자의 dp의 값을 비교해서 더 큰 값이 현재 자기자신의 dp값이된다.

 

코드 

#include <iostream>
using namespace std;
int ary[1001];
int dp[1001];
int N;
int max(int a,int b){
    if(a>=b){return a;}
    else{return b;}
}
void set(void){
    for(int i = 0;i<N;i++){dp[i] = 1;}
}
int main(void)
{
    int temp = -1;
    int result = 1;
    cin >> N;
    for(int i = 0;i<N;i++){
        cin >> ary[i];
    }
    set();
    for(int i = 0;i<N;i++){
        temp = -1;
        for(int j = 0;j<i;j++){
            if(ary[i]>ary[j]){
                if(dp[j]>=dp[i]){
                temp = ary[j];
                dp[i] = dp[j]+1;
                }
            }
        }
        result = max(result,dp[i]);
    }
    cout << result;
}