[BOJ] 11053 가장 긴 증가하는 부분 수열

문제 링크

문제

문제풀이

1. 증가하는 부분 수열이기 때문에 기준 인덱스를 하나씩 옮겨가면서 기준인덱스보다 오른쪽에 있는 것이 부분수열 배열에 있는 마지막 보다 크다면 부분수열에 추가하고 모두 순회하면 부분수열의 len을 출력하게끔 했다. → 문제: 두 칸이상 뒤에 있는 것을 포함해야 최대 증가하는 부분 수열이 되는 케이스가 존재한다. ( 10, 20, 10, 30, 11, 12, 13, 50 ) → 5가 답인데 4가 나옴

2. 배열을 순회하면서 값과 인덱스를 같이 저장해서 값을 기준으로 정렬한 후 1번과 같이 부분 수열을 순회하되 인덱스와 값이 모두커야 부분 수열이 되게끔 저장함 → 문제: 부분수열이 제대로 완성되지 않음 (10, 20, 21, 22, 81, 82, 83, 24, 25, 101, 102, 103 ) → 답은 10인데 9가나옴

3. DP사용
n번째 가장 긴 부분수열의 길이는, 0~n-1번째까지 부분수열중 n의 값보다 작으면서 가장 큰 부분수열의 길이에 1을 더한 것 과 같다.
[ 1 , 2 , 1 , 3 , 4 , 2 ]
3일떄
1 2 3
1 3
2 3 가능한데, 이때 123이 가장 긴 것 이것은 3보다 작은 값 2가 가지는 부분 수열에서 1을 더한것과 갯수가 같은같음
 
4일때
1,2,3,4
1,2,4
1,3,4
14가 가능한데
이때 1234가 가장 긴 것 ㅇ것은 4보다 작은 값 3이 가지는 부분수열에서 에서 1을 더한 것과 갯수가 같음
"이전에 나온 숫자들 중에서 , 현재 값인 '3'보다 작은 값 중에서, 가지고 있는 부분 수열의 길이 중 가장 긴 부분 수열의 길이에 + 1을 한 값이 현재 값에서 발생할 수 있는 가장 긴 증가하는 부분 수열의 길이가 된다."
"x번째 값이 가지는 가장 긴 증가하는 부분수열의 길이를 구하고 싶다면 , 1 ~ x - 1번째 값들 중, x번째 값 보다 더 작은 숫자들이 갖는 부분수열의 길이 중, 가장 길이가 긴 부분수열의 길이에 + 1을 한 값이, x번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이이다."
DP[a] = b 의 의미는 "a번째 값이 가지는 가장 긴 증가하는 부분수열의 길이는 b입니다."

N = int(input())

li = list(map(int, input().split()))

count = 0
DP = [0] * 1001
answer = 0

for i in range(len(li)):
    DP[i] = 1
    for j in range(i):
        if li[i] > li[j]:
            DP[i] = max(DP[i], DP[j]+1)
        
    answer = max(answer, DP[i])
        
print(answer)

• O(N^2)

입력

출력

6
10 20 10 30 20 50

4

알고리즘 분류

• 다이나믹 프로그래밍