[백준] 11053 가장 긴 증가하는 부분 수열 (실버2) / DP

문제요약

나의 코드 및 설명

n = int(input())
num_list = [0] + list(map(int, input().split()))

dp = [0] * (n+1)

for i in range(n+1): #dp 테이블 채우기
    mx = 0
    for j in range(i): #dp 처음 인덱스부터 현재 인덱스-1 까지 값 비교
        if num_list[i] > num_list[j]: #만약 작은 숫자라면,
            mx = max(mx, dp[j]) #최대값을 찾는다
            dp[i] = mx + 1 #찾은 최대값에서 +1 해준 것이 dp[i] 값

print(max(dp))

피드백

DP 알고리즘 연습을 위해 풀어본 문제. LIS는 꽤 유명한 문제라고 한다. 누적된 최대 길이를 저장하는 dp 테이블을 만들고, for문을 통해 dp 테이블을 하나씩 채워가면서 문제를 해결했다. 이전 인덱스에 저장된 값 중 가장 큰 값을 찾아내기 위해서 for문을 한 번 더 사용했다. 아직은 간단하기만 한 문제여서 그런지 DFS, BFS 알고리즘을 배우는 것과는 또 다른 재미가 있다. 간단한 문제라도 여러 번 풀어보면서 dp 테이블을 사용하는 데에 익숙해져야겠다.