[BOJ] 11053. 가장 긴 증가하는 부분 수열

Python3,DP

문제

입출력

입출력 예시

나의 풀이 (시도)

n = int(input())
dp = []
a = list(map(int, input().split()))

for i in range(n):
    if i == 0:
        dp.append(a[0])
    elif a[i] > a[i-1]:
        dp.append(a[i])

print(dp)

주요 포인트

출처: https://zidarn87.tistory.com/285

현재 위치(i)가 이전에 원소(j)보다 클 때, dp값에 1을 더한다.
(단, 현재 위치의 dp[i]가 dp[j]보다 작을 때만 해당한다.)
dp 배열에 있는 수 중 가장 큰 값(max)을 출력한다.

a[i] a[j]
20 10
30 10
30 20
20 10
50 10
50 20
50 30

10의 dp값은 1, 20의 dp값은 2, 30의 dp값은 3, 20의 dp값은 2, 50의 dp값은 4가 된다.

최종 코드

n = int(input())
dp = [0 for i in range(n)]
a = list(map(int, input().split()))

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

피드백

이중 반복문이 필요한 문제였다.
조건식을 a[i] > a[j] and dp[i] < dp[j] 이렇게 잡는 게 포인트였다.