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

11053은 dp문제입니다.

저도 처음에는 잘못 생각해서 틀렸는데,

반례로

5

10 50 20 30 40

오답 : 2

정답 : 4

잘못 생각한 이유는 이전 값보다 큰 값을 가지고 가는 형식으로 10 50을 가지고 최종 답 2를 구했습니다.

하지만 문제는 10 20 30 40 으로 최종 답 4를 구해야 합니다.

 

따라서 구하는 방식은

 

10

10 50

10 20(50을 덮어씀)

10 20 30

10 20 30 40
혹시 잘 이해가 안되시는 분들이 있을 수도 있으니

 

10 60 70 20 30 40 50

를 예로 들면

 

10

10 60

10 60 70

10 20(여기에 덮어씀, 10보다는 크기 때문) 70

10 20 30(70자리에 덮어씀, 20보다는 커서)

10 20 30 40

10 20 30 40 50 이런식으로 구해주면 문제를 풀 수 있습니다.

#include <iostream>
#include <algorithm> 
 
using namespace std;

int n;
int dp[1000] = {};
int arr[1000] = {};
int sum = 0;

int main()
{ 
    scanf("%d", &n); 
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]); 
    for(int i = 0; i < n; i++){
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
        sum = max(sum, dp[i]);
    }
    printf("%d", sum);
}