[백준] 11053번 - 가장 긴 증가하는 부분 수열 (DP) - 결과 포함

www.acmicpc.net/problem/11053

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

처음에는 단순하게 반복문을 돌리면서 이전의 최댓값보다 더 큰 값이 나오면 추가한 다음

전체의 길이를 출력하는 방법을 이용했다.

 

결과적으로 접근법은 유사했으나 문제 이해를 못했던 것 같다.

 

일단 구해야하는 수열은 증가하는 수열이다.

그리고 그 수열 중에서 가장 길이가 긴 수열을 구해야 한다.

 

먼저 각각의 숫자를 순서대로 탐색한다.

증가하는 수열이라고 했기 때문에 순서대로 탐색해야 증가하는지를 알 수 있다.

 

그리고 지금 내가 보고 있는 숫자의 이전 숫자들을 한 번 더 살핀다.

만약 이전의 숫자보다 내가 보고 있는 숫자가 크다면 메모를 수정한다.

 

여기서 메모는 부분 수열의 길이이다. 부분 수열은 최소 1이므로 처음에 모두 1로 초기화한다.

 

예로 나온 A = {10, 20, 10, 30, 20, 50} 의 경우

d = [1, 1, 1, 1, 1, 1] 로 초기화하고 반복문을 시작한다.

 

20은 10보다 크다.

그러므로 d 리스트의 두 번째 원소의 값을 2로 수정한다.

 

이전에 10보다 작은 숫자가 없으므로 1을 유지한다.

 

30보다 작은 숫자는 10과 20이다.

그러므로 길이는 3이 되고

 

마지막 50의 경우 50보다 작은 숫자가 10, 20, 30이므로

길이는 4다.

 

여기서 규칙을 찾을 수 있다.

현재 내가 보고 있는 숫자가 만약 이전의 숫자보다 크다면

이전에 가장 큰 길이보다 1을 더해줘서 저장하면 된다.

 

왜냐하면 이전에 내가 구한 값이 최대 일것이고 지금 내가 보고 있는 숫자가 더 크다면 숫자 하나가 늘어난 것이기 때문이다.

그러나 이전의 값들을 반복문을 통해 처음부터 확인하기 때문에

내가 지금 보고 있는 이전 값의 길이가 최대라는 보장이 없다.

그러므로 지속적으로 현재 내 길이와 이전 길이 + 1 을 비교하면서 더 큰 값을 저장해야 한다.

 

최종적으로 메모한 리스트의 최대 길이를 출력하면 된다.

 

[소스 코드]

n = int(input())

data = list(map(int, input().split()))
d = [1] * n

for i in range(1, n):
    for j in range(i):
        if data[i] > data[j]:
            d[i] = max(d[j] + 1, d[i])

print(max(d))