[python] baekjoon 가장 큰 증가 부분 수열 문제 풀이

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

수열 A가 주어졌을 때, 합이 가장 큰 증가 부분 수열의 합을 출력하시오.

 

 

문제풀이

수열의 크기는 최대 1000으로 주어진다. 

가장 단순한 방법으로는 만들 수 있는 모든 수열을 만들어보고 증가 부분 수열 중 최댓값을 찾는 것이다.

하지만 이 방법은 O(2^1000)이라는 엄청난 시간이 걸린다.

 

이 문제는 부분문제로 쪼갠 뒤 해결할 수 있다.

현재 문제가 인덱스 i부터 시작하는 증가 부분 수열의 최댓값을 찾는 것이라면

인덱스 i에 해당하는 숫자를 고르고 i+1부터 시작하는 증가 부분 수열의 최댓값으로 쪼갤 수가 있다.

기저사례는 모든 수열을 탐색했을 때이다. i가 수열의 길이와 같은 상황

 

메모이제이션 할 리스트를 만들고, 인덱스 i에 해당하는 공간에 i부터 시작하는 증가 부분 수열의 최댓값을 넣어둔다.

그러면 시간 복잡도는  O(N)이 될 것이다.

 

단 숫자가 처음 시작하는 인덱스가 0이 아니라 다른 수일 수 있다.

for문을 통해 0~N까지 모든 숫자에 대해 재귀 함수를 반복하는 방법이 있고,

인덱스 0에 최솟값을 넣은 뒤 재귀 함수를 돌리면 모든 인덱스에서 시작할 수 있다.

마지막 결과값에서 0에 넣은 최솟값을 빼주기만 하면 된다.

 

코드

import sys

def lis(start) :

    # 기저사례 모든 수열을 탐색했으니 0 반환
    if start == N :
        return 0

    if dp[start] :
        return dp[start]

    now = A[start]
    ret = now

    for idx in range(start+1,N) :
        # 현재 인덱스에 해당하는 값보다 큰 값으로만 접근
        if now < A[idx] :
            # 현재 인덱스 값 + idx에서 부터 시작한 증가 수열의 최대값
            ret = max(ret, lis(idx)+now)

    # ( 현재 인덱스 값 + idx에서 부터 시작한 증가 수열의 최대값 )들의 최대값 == 현재 인덱스에서 부터 시작한 증가 수열의 최대값
    dp[start] = ret

    return dp[start]


N = int(sys.stdin.readline().rstrip())
A = list(map(int,sys.stdin.readline().rstrip().split()))

# 인덱스 0에 수열의 최소값을 넣어준다.
A.insert(0,-1)
N += 1

maxLen = 0

dp = [None for _ in range(len(A))]

# 수열의 최소값이 포함된 결과이므로 최소값을 다시 빼준다.
print(lis(0)+1)

 

초기 접근 방식과 오답의 원인

문제를 쪼개는 방식은 이해했지만 최댓값을 얻기 위해 재귀 함수 내에서 어떻게 처리해야 할지 몰랐다.

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.