[백준] 11053 (실버2)

이번 문제는 DP 문제이고, 나는 개인적으로 DP가 너무 어렵다,,,

# dp
n = int(input())
arr = list(map(int, input().split()))

dp = [1] * n

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

print(max(dp))

수열의 크기만큼 dp테이블을 만든다.
dp테이블의 초기값이 1인 이유는, 각각에 해당하는 수열의 길이를 의미한다.
즉. {10, 20, 10, 30, 20, 50}에 대하여 각각의 dp테이블 값은 1이다. (수열의 길이가 1이기 때문이다.)
dp 테이블에는 증가하는 수열의 길이를 저장한다.
dp[0]는 10에 대하여 증가하는 수열의 길이가 1이다.
dp[1]은 10과 20, 증가하는 수열의 길이가 2이다.
dp[2]는 10에 대하여 증가하는 수열의 길이가 1이다.
dp[3]은 10, 20, 30에 대하여 증가하는 수열의 길이가 3이다.
dp[4]는 10, 20에 대하여 증가하는 수열의 길이가 2이다.
dp[5]는 10, 20, 30, 50에 대하여 증가하는 수열의 길이가 4이다.
따라서 가장 긴 증가하는 부분 수열의 길이는 4이다.

i와 j에 대한 비교는 현재 위치 i와 그 이전의 모든 위치 j에 대한 비교를 하는 것이다.
j 위치의 값이 i 위치의 값보다 작아야만 dp 테이블이 갱신된다.
만약 작다면, 현재 위치 이전의 숫자 중 dp 최댓값에 1을 더해주면 된다. (현재 위치를 포함시키는 의미)

이 문제는 어렵다...
dp문제는 아직 나한테 너무 어렵다...