[백준알고리즘/11053번/파이썬] 가장 긴 증가하는 부분 수열

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

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

DP.. 정복까진 아니더라도 어느정도 풀 수 있는 정도로까지 올리기도 만만치 않네요..

아직 알고리즘 개념에 대한 이해가 부족한 것인지 컴퓨팅적 사고력이 부족한 것인지 조금 더 스스로 되돌아보고 부족한 부분을 찾아봐야겠습니다.

 

문제: 주어진 수열에서 가장 길게 증가하는 부분 수열의 길이를 구하는 문제입니다.

 

풀이 방법: 다이나믹 프로그래밍

 

풀이 코드:

import sys

n = int(input())
array = list(map(int,sys.stdin.readline().rstrip().split()))

dp = [1]*(n+1)

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j]+1 > dp[i]:
            dp[i] = dp[j]+1

print(max(dp))

 

풀이 설명:

dp = [1]*(n+1)

첫번째로 모든 수열의 길이는 자기 자신만 해도 길이가 1이 되므로 길이를 저장할 배열 dp를 1로 초기화 해주었습니다.

 

그럼 수열의 길이는 어떻게 구할까요? 

 

예를 들어, 10 20 30 40 50 인 수열이 있다고 해보겠습니다.

 

10	20	30	40	50
1	2	3	4	5

10으로 만들 수 있는 수열은 1이 되겠죠.

 

그럼 20으로 만들 수 있는 수열은 자신보다 작은 수인 10을 통해 {10, 20} 을 만드는 것입니다.

 

30으로 만들 수 있는 수열은 자신 보다 작은 수인 [10,20]을 통해 {10, 20, 30}을 만든 것이구요.

 

그럼 다음과 같은 결론을 얻을 수 있습니다.현재 수로 만들 수 있는 제일 긴 수열의 길이는 자신보다 작은 수 중에서 제일 큰 수 (현재 값이 30인 경우, 20을 의미함.)로 만들 수 있는 수열의 길이 + 1이라는 것을요.

 

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j]+1 > dp[i]:
            dp[i] = dp[j]+1

 

 

 

 

따라서, 코드를 다음과 같이 구현하였습니다.

현재 값( array[ i ] )보다  작은 값 ( array [ j ] )이 있을 경우, dp[i] = dp[j] + 1로 해주었습니다.

다만 조건문에 dp[ j ] + 1 > dp[ i ]라는 조건을 담아, dp[ j ] 에 해당되는 수열의 길이 중 제일 큰 값이 dp [ i ]에 담기도록 하였습니다.