BOJ_14002 [ 가장 긴 증가하는 부분 수열 4 ] [ 파이썬 ]

문제

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

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

문제 해결 방법

다이나믹 프로그래밍으로 문제를 해결해야 된다.

범위가 1000이기 때문에 2중 포문을 통해서 가장 긴 값을 갱신해주면 된다.

DP[현재 인덱스] = Date[기존인덱스] < Date[현재인덱스]  and DP[기존인덱스] + 1 > DP[현재인덱스] 

인 경우에는 DP[현재 인덱스] 값을 갱신해준다.

 

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_14002.py

jokerKwu/BOJ_Algorithm

import sys
input = sys.stdin.readline

N = int(input())
date = list(map(int,input().split()))
date.insert(0, 0)

dp = [ 1 for _ in range(1002) ]
dp[1] = 1
answer_value = dp[1]
for i in range(2, N+1):
    for j in range(1, i):
        if date[i] > date[j] and dp[i] < dp[j] + 1:
            dp[i] = dp[j] + 1
            if dp[i] > answer_value:
                answer_value = dp[i]

value = answer_value
answer_arr = []
for i in range(N, 0, -1):
    if dp[i] == value:
        answer_arr.append(date[i])
        value -= 1

print(answer_value)
for i in range(len(answer_arr)-1, -1, -1):
    print(answer_arr[i], end=' ')