[BAEKJOON][Python] 11053 - 가장 긴 증가하는 부분 수열

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

---

✏️ 1차 시도

📝 접근

• 백트래킹을 사용한 Brute Force 방식이다.

✨ 소스 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def solve(start, subsequence):
    ans = 0
    for i in range(start, n):
        if len(subsequence) == 0 or subsequence[-1] < array[i]:
            subsequence.append(array[i])
            ans = max(ans, solve(i + 1, subsequence))
            subsequence.pop()
    return max(ans, len(subsequence))

n = int(input())
array = list(map(int, input().split()))
print(solve(0, []))

---

✏️ 2차 시도

📝 접근

• 2차 시도에서는 메모이제이션을 사용했다.

• 이전의 solve 함수는 정수의 배열을 입력받고 있으므로 메모이제이션을 적용하기 까다롭다. 이번 시도에서는 array[start]에서 시작하는 부분 증가 수열 중 가장 긴 것의 길이를 반환한다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def solve(start):
    result = memo[start]
    if result != -1:
        return result

    result = 1
    for next in range(start + 1, n):
        if array[start] < array[next]:
            result = max(result, 1 + solve(next))
    return result

n = int(input())
array = list(map(int, input().split()))
memo = [-1] * n
print(max(solve(i) for i in range(n)))

---

✏️ 3차 시도

📝 접근

• 3차 시도에서는 상향식 동적 계획법을 사용했다. LIS 문제를 동적 계획법으로 풀이하는 가장 통상적인 방법이다.

• 현재 원소 전에 있으면서 현재 원소보다 작은 원소들이 존재한다면, 해당 원소들의 테이블의 값 중 가장 큰 것을 사용하면 된다.

✨ 소스 코드

import sys
input = sys.stdin.readline

n = int(input())
array = list(map(int, input().split()))
tab = [1] * n

for i in range(n):
    for j in range(i):
        if array[i] > array[j]:
            tab[i] = max(tab[i], tab[j] + 1)
print(max(tab))