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

문제

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

입력

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

• 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

입력 예제

6
10 20 10 30 20 50

출력 예제

4

문제 풀이

• 간단하게 앞 뒤 숫자를 비교하여 뒤에 있는 숫자가 더 큰 경우 인덱스의 값을 증가시켜준 후, dp리스트에서 최댓값을 출력하면 가장 긴 증가하는 부분 수열의 값을 뽑아낼 수 있다.
• 따라서 점화식은 아래와 같다.

# j < i
if array[j] < array[i]: dp[i] = max(dp[i], dp[j] + 1)

• J값은 항상 0부터 돌게 되므로, 0번쨰 인덱스부터 i번쨰 인덱스까지 다시 처음으로 돌아가 비교를 마친 후, dp[i]에 값을 갱신하여 넣어준다. 따라서 dp[i]에 이미 들어있는 값과, 이전 인덱스에 1을 더한 값을 항상 비교해서 값을 넣어주어야 올바르게 출력할 수 있다.

코드

n = int(input())
array = list(map(int,input().split()))
dp = [1] * 1001
# i, j 값 비교
for i in range(1, n):
    for j in range(i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))