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

www.acmicpc.net/problem/11053

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

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

⊙ 문제 접근 과정

 

LIS 문제... 블로그에서 2번째로 다룬다.

생각보다 꽤 중요한 알고리즘으로 느껴졌고 이번 기회에 집중해서 파봤다.

 

전에 DP 문제를 풀 때 tooo1.tistory.com/121 풀었었는데 이번에도 DP 문제에서 또다시 나왔다.

DP에 자주 나오는 문제라고 느꼈고 그냥 넘어가선 안 된다고 생각했다.

 

LIS에 대한 자세한 설명은 위 링크에서 확인하자!

 

아래 풀이는 O(N^2) 풀이법이다. O(N log N) 풀이법도 있다.

하지만 이번 문제에서는 제한이 널널하여 비교적 구현하기 쉬운 시간 복잡도 O(N^2)으로 풀었다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <algorithm>

#define SIZE 1000
using namespace std;

int a;
int max_value=0;
int arr[SIZE];
int dp[SIZE];

int main() {
    cin >> a;
    for(int i=0;i<a;i++) {
        cin>>arr[i];
    }

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

 

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

LIS 그냥 넘어가지말자

 

좋아요는 로그인하지 않아도 누를 수 있습니다!