백준(baekjoon) 11053번: 가장 긴 증가하는 부분 수열(실버 2, 파이썬 PYTHON) - 동적 계획법 1

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

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

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

 

import sys

N=int(sys.stdin.readline())
lst=list(map(int,sys.stdin.readline().split()))
dp=[0]*N

for x in range(N):
  for y in range(x):
    if(lst[x]>lst[y] and dp[x]<dp[y]):
      dp[x]=dp[y]
  dp[x]+=1

print(max(dp))

 

※ 동적 계획법 1

 

 

● 먼저 수열 A의 크기 N을 입력받은 후, 뒤에 입력들을 lst 배열에 차례대로 넣어준다. 그 후 lst 배열의 각 요소를 수열의 끝 요소로 하는 가장 긴 증가하는 수열의 길이를 담아줄 초기값이 0이고 크기가 N인 배열 dp를 정의해준다.

 

● 변수 x는 0부터 N-1까지, 변수 y는 0부터 x-1 까지 돈다.(y는 인덱스 x 인 lst 원소보다 앞에있는 원소들을 접근하게 된다.)

만약 lst[x] 가 lst[y] 보다 크고( lst[x] 가 더 크다면, lst[y] 를 포함하는 가장 긴 증가하는 수열 뒤에 lst[x]를 이어붙여도 증가하는 수열을 만족하게 된다.), dp[x] 보다 dp[y] 가 더 크면, dp[x] 에 dp[y] 의 값을 넣어준다.(이전에 고려하였던 상황보다 현재 lst[y] 를 포함하는 가장 긴 증가하는 수열 뒤에 lst[x] 를 붙이는 것이 더 길다면, dp[x] 에 dp[y]의 값 넣어줌.)

 

● y for문이 다 돌면, 현재 dp[x] 에는 lst[x] 가 뒤에 들어가도 증가하는 수열을 만족하는 증가하는 수열 중 가장 긴 수열의 길이가 들어가 있다. 이 수열에 lst[x] 를 뒤에 붙이면 길이가 1 증가하므로 dp[x]+=1 연산을 해준다.

 

● 마지막으로 dp 배열에 담겨있는 모든 값 중 가장 큰 값을 출력하면 가장 긴 증가하는 부분수열의 길이를 구할 수 있다.

 

 

결과