백준 11053 가장 긴 증가하는 부분 수열 (파이썬)

30 Mar 2021 in Dev on BOJ

11053 가장 긴 증가하는 부분 수열 문제 바로가기

접근방식

수열의 처음부터 끝까지 돌며 현재 인덱스 이하의 인덱스들을 다 체크하는 방식이다.
주석에 보다 자세한 설명을 적어두었다.

파이썬 코드

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dp=[0 for i in range(n)]

for i in range(n):
    for j in range(i):
        # index 0부터 i-1까지 arr와 dp값을 비교한다
        # arr[i]가 arr[j]보다 큰데 dp[i]는 작을 경우 dp[i] 값을 dp[j]로 바꿔준다.
        # (값은 큰데 카운트 값은 작은 경우)
        if arr[i] > arr[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    # 조건없이 +1을 한다.
    dp[i] = dp[i] + 1

print(max(dp))