[BaekJoon 11053 : 동적계획법, Python] - 가장 긴 증가하는 수열2

2021, Nov 01    


백준 11053 가장 긴 증가하는 수열2 : 실버 2



Solution


DP Memoization 활용(Bottom-up)


import sys
input = sys.stdin.readline

n = int(input())
nums = [-1]
nums += list(map(int, input().split()))

DP = [0 for _ in range(n+1)]     # i 번째 숫자까지 최장 수열의 길이

for i in range(1, n+1):
    for j in range(1, i):
        if nums[j] < nums[i]:
            DP[i] = max(DP[j]+1, DP[i])

print(max(DP) + 1)


풀이과정 및 느낀점


가장 기본적인 형태의 memoization 을 활용하는 DP문제이다.
주의해야 할 부분은 처음엔 DP[1] 만 1로 설정해주면 항상 첫 시작 숫자까지도 포함한 수열길이가 나올 거라고 생각하고 첫 번째 숫자가 증가수열에 포함이 안 된 경우를 고려하지 못했다.
처음에 ‘틀렸습니다’ 가 나오고 나서야 최종 출력에서 max(DP) + 1 을 해주었다.

# BaekJoon # Python # DP # 동적계획법 # Dynamic Programming # Algorithm