boj 11053 : 가장 긴 증가하는 부분수열

문제 주소: https://www.acmicpc.net/problem/11053

난이도: silver 2

1.문제설명

• 가장 긴 증가하는 부분 수열의 길이를 찾아라

2.문제해결 아이디어.

• 1차원 그리드(테이블)를 생성해서 풀어보자
• cache[i] = i번째 원소가 가지는 가장 긴 증가하는 부분 수열의 길이
• 이중 for문으로 피벗을 정하고, 피벗 이전의 값들과 비교해서 피벗의 값이 더 크면
• 점화식을 통해 값을 할당한다.

3.문제접근법

아래가 핵심코드

for i in range(1,N): # 피벗 설정
    for j in range(i): # 피벗 이전의 숫자들을 순회하면서
        if numbers[j] < numbers[i]: # 피벗과 크기 비교
            cache[i] = max(cache[i], cache[j]+1) 

4.특별히 참고할 사항

• 딱히 없음
• 시간복잡도는 O(N^2)

5.코드구현

N = int(input())
numbers = list(map(int, input().split()))
cache = [1] * (N)

for i in range(1,N):
    for j in range(i):
        if numbers[j] < numbers[i]:
            cache[i] = max(cache[i], cache[j]+1)

print(max(cache))