Algorithm 문제 & 공부/DP
백준 11053번 파이썬
somm12
2022. 8. 11. 10:25
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
가장 긴 증가 부분 수열을 찾는 것으로,
각 수열 요소보다 작은 요소들의 수열 길이 중 가장 큰 것 +1 을 하는 방식으로 문제를 풀 수 있다.
| arr | 10 | 20 | 10 | 30 | 20 | 50 |
| dp | 1 | 2 | 1 | 3 | 2 | 4 |
주어진 수열에서 증가수열 & 수열의 길이가 최대가 되어야한다.
그렇다면 dp를 이용해서 현재까지 가장 수열의 길이가 큰 것을 차근차근 구하고, 이를 배열에 저장한다. 현재 요소보다 작은 수들의 수열길이 중 최대 수열의 길이 +1 을 하는 방식으로 문제를 풀 수 있다.
n = int(input())
arr = list(map(int,input().split()))
dp = [0] * n
length = -1
dp[0] = 1
for i in range(1, n):
for k in range(i):
if arr[i] > arr[k]:
if dp[k] > dp[i]:
dp[i] = dp[k]
dp[i] += 1
print(max(dp))