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

문제

백준 11053번 - 가장 긴 증가하는 부분 수열

해결 과정

• DP로 풀기
• dp: num[i] 를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이
• ex) 이중포문 비교: 10 20 10 30 20 50
  i vs j
  20 vs 10
  10 vs 10, 20
  30 vs 10, 20, 10...
• dp[i]와 dp[j] + 1 중에 큰 값을 dp[i]

시행착오

• 문제를 잘못이해함 -> 가장 긴 증가하는 부분 수열 -> 연속x

import sys

n = int(sys.stdin.readline())
num = list(map(int,sys.stdin.readline().split()))
dp = [1] + [0] * (n-1)

for i in range(1,len(num)):
  if num[i] > num[i-1]:
    dp[i] = dp[i-1] + 1 
  else:
    dp[i] = dp[i-1]

print(dp[-1])

풀이

import sys

n = int(sys.stdin.readline())
num = list(map(int,sys.stdin.readline().split()))
dp = [1] * n

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


print(max(dp))