[백준] 11053번 가장 긴 증가하는 부분 수열 (LIS문제)

사용 언어 - Python3

문제 -  11053번 가장 긴 증가하는 부분 수열

LIS/LCS 문제 : 가장 긴 증가하는 부분 수열

LIS (Longest Incresing Subsequence)

LCS (Longest Common Subsequence)

 

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

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

 

 

정답

해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기

dp[i] = max(dp[i], dp[j]+1)

해당 위치에서 나보다 더 작은 숫자가 있으면 dp 값을 업데이트해준다.

=> 나보다 작은 숫자가 여러 개 있다면, 자동으로 그 중 가장 큰 값 + 1

수열 A	10	20	10	30	20	50
dp(디폴트가 1)	1	2	1	3	2	4
나보다 작은 숫자 있으면 +1		10 확인	10 20 확인	10 20 10 확인 10 있음 1+1 = 2 20 있음 2 +1 = 3	10 20 10 30 확인 10 있음 1+1 = 2 20 pass 10 있음 1+1 = 2 30 pass	10 20 30 20 20 확인 3+1 = 4
max(dp) = 가장 긴 증가하는 부분수열 길이 = 4

 

n = int(input())
arr = list(map(int,input().split()))
dp = [1 for _ in range(n)]

for i in range(n):
    for j in range(i): # 내 기준 왼쪽에 있는 숫자까지 확인
        if arr[i] > arr[j]:
            dp[i] = max(dp[i],dp[j]+1)

print(max(dp))

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/11053_%EA%B0%80%EC%9E%A5%EA%B8%B4%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4.py