BOJ/백준-11053-python

문제📖

풀이🙏

• 첫째 줄에 수열 A의 크기 N이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 A(i)가 주어진다.
• 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력하라.
• DP 알고리즘 문제이다.
• DP 문제이므로 처음에 배열을 선언해준 뒤, 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이므로 max(dp)를 사용하면 된다.
• 이중 for문 + if 조건문으로 구현하였다.

코드💻

# boj, 11053 : 가장 긴 증가하는 부분 수열, python
# dp : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
import sys

def DP(A):
    for i in range(N):
        for j in range(i):
            if all((A[i] > A[j], d[i] < d[j])):
                d[i] = d[j]
        d[i] += 1
    return max(d)

N = int(sys.stdin.readline())
A = list(map(int, input().split()))
d = [0] * N

print(DP(A))

결과😎

출처 && 깃허브📝

https://www.acmicpc.net/problem/11053
github