[백준 14002번] 파이썬 - 가장 긴 증가하는 부분수열 4

시간초과 1초, 메모리 제한 256MB

[백준 14002_가장 긴 증가하는 부분 수열4)(https://www.acmicpc.net/problem/14002)

조건

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

접근 방법

• N^2의 시간복잡도로도 풀 수 있으므로 DP를 사용해준다.
• 배열의 길이 만큼의 for문, 해당 배열원소 직전까지의 for문 1개를 사용해준다.
• 만약 arr[j]가 arr[i]보다 크다면
• dp[i] = max(dp[i]+1, dp[j])로 갱신해준다.
• 또한, 정답 수열을 뽑아줘야 하므로 order =max(dp)를 사용해준다.
• 전체 배열길이만큼 n-1부터 0번까지 돌아준다.
• 이 때, dp[i] == order이라면
• subsequence 배열에 추가해주고, order -= 1을 해준다.
• 큰 수부터 더했으므로
• reverse 후 출력해준다.

import sys  
sys.stdin = open('input.txt')  
N = int(input())  
input_array = list(map(int, input().split()))  
dp = [1] * N  # 최장수열 길이를 저장할 dp 리스트선언  

for i in range(N):  # 배열 길이만큼돈다.  
    for j in range(i):  # 해당 배열 원소의 직전 원소까지 돈다.  
        if input_array[i] > input_array[j]:  # 만약 해당 원소가 전 원소보다 크다면  
            dp[i] = max(dp[i], dp[j] + 1)  
            # 전 원소에 저장되어 있는 최장수열길이에서 +1 값과 저장되어있는 수열길이값을 비교해서 큰값을 대입  

print(max(dp))  # 최장길이 출력  

subsequence = [] #정답수열 입력할 배열선언  
order = max(dp)  # max(dp) 값을 저장  
for i in range(N - 1, -1, -1):  
    if dp[i] == order:  # 만약 dp[i] 값이 order값과 같다면  
        subsequence.append(input_array[i])  # 해당 input_array[i]값을 추가  
        order -= 1  # 해당 order 값을 1씩 감소시킨다.  

subsequence.reverse()  # 큰수부터 작은수로 뽑았기 때문에  
print(*subsequence) #정답수열 출력