[BAEKJOON 백준] 11053 가장 긴 증가하는 부분 수열 (PYTHON)

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

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

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

DP(Dynamic Programming)을 활용해서 문제를 해결했다. 2중 for문을 돌면서 부분 수열이 가장 길어질 때를 찾게 된다.

 

1. dp[i]의 값을 1로 초기화를 한다.

2. 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없음)

3. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면 된다.

 

예를 들어 i = 4일때를 확인해보자.

i = 4 j = 0 dp[4] =1

arr[4] > arr[0] true 이므로 dp[4] = max(dp[4], dp[0] + 1) 2이다.

i = 4 j = 1 dp[4] = 2

arr[4] > arr[1] false

i = 4 j = 2 dp[4] = 2

arr[4] > arr[2] true이므로 dp[4] = max(dp[4], dp[2] + 1) 2이다.

i = 4 j = 3 dp[4] = 2

arr[4] > arr[3] false

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

4. dp배열의 원소중 가장 큰 원소를 출력한다.

정답은 4가 된다.

 

x = int(input())

arr = list(map(int, input().split()))

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))