BOJ 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053
시간 1초, 메모리 256MB
input :

• N(1 <= N <= 1,000)
• Ai (1 <= Ai <= 1,000)

output :

• A의 가장 긴 증가하는 부분 수열의 길이를 출력.

조건 :

• 수열 A = {10, 20, 10, 30, 20, 50} 인 경우 / A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4

---

처음엔 경우의 수를 따지려 했다. 그러다가. 어차피 반복문 2번 돌리면 풀리지 않을까? 싶었고 나는 숫자를 비교하려는 곳에서 막혔다.
시작하는 지점부터 숫자를 교체 하며 비교를 하려 했기 때문인데.

이와 반대로 가장 뒤에 존재하는 숫자를 고정해놓고.
이것보다 작은 숫자들의 개수를 세아리는 것이 옳은 방법이다.

길이를 세아릴 때 자기자신도 들어가야 함으로 dp는 1로 모두 초기화 한다.

동작 과정

1. dp[i]의 값을 1로 초기화

2. 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없음)

3. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면 된다. (j의 원소보다 큰 i가 하나 더 생기기 때문에 1을 더한다고 보면 된다)

dp 안에서 max 값이 수열의 최대 길이를 나타내지. 가장 뒤의 아이템이 최대 길이를 나타내지 않는다.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp = [1] * n

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

print(max(dp))