백준 11053 가장긴증가하는부분수열

너무 심심해서...코테 문제나 풀어야겠다. 하고 푸는중..

dp는 그냥 기억하면서 풀기인데, 왜이렇게 어렵게 느껴지는지 모르겠다.
나는 항상 dp가 무서워서 dp를 잘 안푸는 편인거같다.. ㅜㅠ
그래도 평생 피할수는 없으니까 하나씩 해보쟛!

dp라고 생각하고 dp문제를 풀면 좀 할만한데,
그냥 봤을때 dp를 떠올리기가 어려운거같음.. ㅜㅠ

그림을 그려서 생각해보면 바로 풀리는 문제였음.
아래와같이 그림 그려서 하나씩 하다보니 해결이 되었다.
저렇게 확인하는데 까지 여러번 머리를 굴렸다...
12345넣어보기도 하고...^^;;

dp는 대부분 코드는 간단하니까, 엄청 짧음...

import sys
input = sys.stdin.readline

N = int(input())

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

dp = [1] * N

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