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

백준

 

---

🤔문제 이해

i+1번째 수가 i번째 수보다 큰 부분 수열 중에서 가장 긴 수열의 길이를 출력하는 문제이다.

---

💡첫번째 아이디어

처음엔 부르트 포스가 생각났다. 그냥 눈으로 계산해봐도 모든 조합을 생각해봐야 풀린다고 생각했기 때문이다.

근데 저걸 처음부터 모든 조합을 다 계산하게 되면 1초는 거뜬히 넘기게 된다...

 

💡두번째 아이디어

멘토님에게 LCS(longest increasing subsequence)를 푸는 방법을 전수받았다!

풀이에 자세히 설명하겠다.

 

🔥풀이🔥

입력받은 수열은 arr에 순서대로 저장해놓고 dp 배열을 arr값으로 초기화해준다.

수열의 두번째 수부터 n번째 수까지를 나타내는 인덱스 i와 첫번째 수부터 i번째 수까지를 나타내는 인덱스 j가 있다고 하자.

만약 arr[j]가 arr[i]보다 작다면, 즉 증가한다면 dp[i]와 dp[j] + 1 중에서 더 큰 값을 dp[i]에 넣어준다.

 

=> dp[i]는 i번째 수를 수열의 마지막 수로 했을 때 가장 긴 증가하는 수열을 의미

---

#include <iostream>
#include <cmath>

using namespace std;
int n;
int arr[1001];
int dp[1001];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;

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

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

    int ans = dp[0];
    for (int i = 1; i < n; i++) {
        if (ans < dp[i]) ans = dp[i];
    }
    cout << ans;


}