[백준] 11055번 가장 큰 증가하는 부분 수열 ★★

💡문제접근

• 종이에 표를 그려가면서 각각의 경우에 대한 답을 찾아서 해결할 수 있었다.
• 다이나믹 프로그래밍 문제를 보면 무조건 겁먹지말고 2차원 배열을 이용하는 방식으로 접근하거나 표를 그려서 최적의 해를 찾도록 해보자.

💡코드(메모리 : 31256KB, 시간 : 236ms)

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().strip().split()))

dp = [0] * N
dp[0] = A[0]

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j] + A[i])
        else:
            dp[i] = max(dp[i], A[i])
print(max(dp))

1	100	2	50	60	3	5	6	7	8
1	101	3	53	113	6	11	17	24	32

💡소요시간 : 27m