[python] 백준 11053 - 가장 긴 증가하는 부분 수열

출처 : 백준, https://www.acmicpc.net/problem/11053

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

 

# 숫자 리스트가 주어진다

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

 

---

 

풀이

 

def solution(n, num_list):
    # 이전에 있는 것들 중 나보다 작으면서 최대 길이가 가장 큰 것

    dp = [1 for _ in range(n)]

    for i in range(1, n):
        # 나보다 작은 idx 중에
        # 가장 긴 길이를 찾아서 + 1
        for j in range(i):
            if num_list[j] < num_list[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

n = int(input())
num_list = list(map(int, input().split()))

print(solution(n, num_list))

---

 

알게 된 점

 

가장 큰 길이를 찾을 필요가 없다.

 

그냥 0부터 i-1까지 돌면서 계속 최대 길이를 업데이트해주면

가장 마지막 값이 최대 길이이다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들