[백준] 11053번 문제 (가장 긴 증가하는 부분 수열) 파이썬(Python) 풀이

n = int(input())
nums = list(map(int, input().split()))
dp = [1] * n

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

print(max(dp))

dp문제이며, 직관적으로 풀 수 있는 문제다.

 

for문이 이중으로 있는데,

바깥 for문은 0 ~ n - 1까지 반복되고,

안쪽 for문은 0 ~ 바깥 for문의 인덱스 - 1까지 반복된다.

 

그러면서 nums[i] > nums[j] 가 성립되면 dp[i]에 dp[j] + 1을 할당하며 수열의 크기를 점진적으로 더하며 구한다.