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

코드 작성

n = int(input())
dp = [1 for _ in range(1001)]
arr = list(map(int, input().split()))
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

코드  풀이

# 문제풀이1

dp 테이블에는 모든 값을 1로 세팅한다.

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

예를 들어, dp[3]을 구하기 위해서는

for 구문에서

i = 3, j = 0 일 때 dp[3] = max(dp[3], dp[0] + 1) 임에 따라 2가 된다

i = 3, j = 1 일 때 dp[3] = max(dp[3], dp[1] + 1) 임에 따라 3이 된다 (dp[1]=2)

i = 3, j = 2 일 때 dp[3] = max(dp[3], dp[2] + 1) 임에 따라 3이 된다

 

dp 값은 [1, 2, 1, 3, 2, 4]이다.

 

 

 

# 문제풀이 2

i = 0일 때

  if 조건 만족 안 함, dp[0] = 1

i = 1일 때

  j가 0일 때 if 조건 만족, dp[1] = dp[0] = 1

i = 2일 때

  if 조건 만족 안 함.

  for문 j가 끝나고 dp[2] = dp[2] + 1 = 1

i = 3일 때

  j가 0일 때 if 조건 만족, dp[3] = dp[0] = 1

  j가 1일 때 if 조건 만족, dp[3] = dp[1] = 2

  for문 j가 끝나고 dp[3] = dp[3] + 1

i = 4일 때

  j가 0일때, dp[4] = dp[0] = 1

  for문 j가 끝나고 dp[4] = dp[4] +1

i = 5일 때

  j가 0,1,2,3일때 만족, dp[5] = dp[3] = 3

  for문 j가 끝나고 dp[5] = dp[5] + 1