해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 11053 가장 긴 증가하는 부분 수열 - dp

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

풀이

1. dp로 풀 수 있는 문제입니다.
2. dp 리스트에 자신을 포함하여 만들 수 있는 부분 수열 크기를 저장합니다.

3. 현재 위치(i)가 이전에 있는 원소(j)가 큰지를 확인한다.

4. 크다면, 그 위치의 dp값에 1을 더해주면 됩니다.
(단, 현재 위치의 dp[i]가 dp[j]보다 작은 경우에만 적용합니다.)

5. 마지막에는 dp에 있는 값중 max를 출력하면 됩니다.

전체 코드

n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
    #print(dp)
print(max(dp))