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

www.acmicpc.net/problem/11053

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

 

수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 코드를 짜야한다!

 

10	20	10	30	20	50
1	2	1	3	2	4

 

방식은 우선 수열을 for문을 돈다. 그리고 맨 처음부터 해당 수까지 for문을 돌면서 자신보다 작은 아이가 있다면!

해당 dp의 수에 +1을 한 것과 현재 dp의 수를 비교하여 더 큰 값을 저장해준다. 그렇게 되면 앞에서 자기보다 작으면서 증가하는 부분 수열을 구할 수 있기 때문이다...

 

사실 이러한 방법은 처음 접해보는 방식이었기 때문에! ㅜㅠㅜㅠ 다른 포스팅들을 참고했다...! dp로 최소값과 최대값을 찾는게 왜인지 너무 어렵게 느껴진다... 반복학습 하다보면 익숙해질까아아~🙏

 

#include <iostream>
#include <vector>

using namespace std;

int arr[1001];
vector<int> dp(1001, 1);

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[j] + 1, dp[i]);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
        
    cout << ans << endl;
    return 0;
}