-
[Python]백준 11053/가장 긴 증가하는 부분 수열/LIS/dpalgorithm/문제 2022. 3. 13. 13:01반응형
https://www.acmicpc.net/problem/11053
⚡️ 문제 설명
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
⚡️ 해결 방법
가장 긴 증가하는 부분 수열 Logest Increasing Subsequence (LIS) 는 전형적인 dp의 문제이다.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
Dp[i]= A[i]를 마지막 원소로 가지는 부분 수열의 최대길이
라 가정하면
점화식은 (모든 0<=j<i 에 대하여)
if A[j]<A[i]
Dp[i] = max(Dp[i], Dp[j]+1)
10 20 10 30 20 50 i=0 1 1 1 1 1 1 i=1 1 2 1 1 1 1 i=2 1 2 1 3 1 1 i=3 1 2 1 3 2 1 i=4 1 2 1 3 2 4 ⚡️ 코드
import sys input = sys.stdin.readline N=int(input()) A=list(map(int,input().split())) dp=[1]*N for i in range(1,N): for j in range(0,i): if(A[j]<A[i]): dp[i]=max(dp[i],dp[j]+1) print(max(dp))
반응형'algorithm > 문제' 카테고리의 다른 글
[Python]백준 13335번/트럭/queue (0) 2023.03.29 [Python]백준 11441/합 구하기 / 누적합 (0) 2022.03.14 [Python]백준 14502/연구소 / 조합 / 배열 복사 copy (0) 2022.03.12 [Python]백준 15649/N과 M(1)(2)(3)(4) / itertools (0) 2022.03.12 [Python]백준 9184/신나는 함수 실행/dp정리/top-down (0) 2022.03.10