[백준] 11053. 가장 긴 증가하는 부분수열 - 파이썬

N = int(input())
nums = list(map(int,input().split()))
dp = [1]*N
for i in range(N):
    for j in range(i): #이전까지 작았다면 해당 dp것에 +1해서 max값 넣기
        if nums[i] > nums[j]:
            dp[i] = max(dp[i],dp[j]+1) #메모이제이션
print(max(dp))

---

처음 dp배열을 1로 세팅해준다. 이유는? 각 원소값이 자기자신이여도 한번 카운트 된다 생각하기 때문

초기

nums = [10, 20, 10, 30, 20, 50]

dp = [1,1,1,1,1,1]

이중 배열로 비교 대상 원소nums[i]보다 그전에 있었던 배열의 원소가 작았던게 있으면 그 비교 대상이 더 큰거니까 +1 해주면서 최댓값을 찾으며 i만큼 반복문을 돈다.

예를 들어 i=1일때 dp는 =[1,1,1,1,1,1]이고 nums[1] > nums[0]이므로 dp[1] = max(dp[1],dp[0]+1)을 통해 dp[1] = 2가 된다. dp = [1,2,1,1,1,1]

i = 2일 때 nums[2] > nums[0], nums[2] > nums[1] 이 성립하지 않음 따라서 dp = [1,2,1,1,1,1]으로 변하지 않음

i = 3일 때 num[3] > nums[0] 이므로 dp[3] = max(dp[3],dp[0]+1)을 통해 dp[3] = 2가 된다. dp = [1,2,1,2,1,1]

              num[3] > nums[1] 이므로 dp[3] = max(dp[3],dp[1]+1)을 통해 dp[3] = 3이 된다. dp = [1,2,1,3,1,1]

              num[3] > nums[2] 이므로 dp[3] = max(dp[3],dp[2]+1)을 통해 dp[3] = 3이 된다. dp = [1,2,1,3,1,1]

...이런식으로 각 dp배열의 메모이제이션한 값과 비교해가며 dp를 갱신해준다.

최종

dp = [1, 2, 1, 3, 2, 4]