PS/Python
[Python] 백준(BOJ) 11053번: 가장 긴 증가하는 부분 수열 - dp
yoo.o
2020. 11. 4. 17:46
반응형
문제
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
풀이
LIS(Longest Increasing Subsequence)를 구하는 문제
왼쪽부터 하나씩 돌면서
나보다 왼쪽에 있으면서 나보다 크기가 작은 애들중 가장 dp[i]가 큰 애에 1을 더해주면 된다.
import sys
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split(" ")))
dp = [0 for _ in range(n)]
for i in range(len(numbers)):
for j in range(len(numbers[:i])):
if numbers[i] > numbers[j] and dp[i] < dp[j]:
dp[i] = dp[j]
dp[i] += 1
print(max(dp))
반응형