📝 BOJ - 가장 긴 증가하는 부분 수열

문제

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

접근 방법

$N$의 길이를 가진 수열이 있을 때 가장 긴 부분 수열의 길이를 구하는 문제이다.

설명

문제의 예시인 10, 20, 10, 30, 20, 50을 가지고 생각해보자. 여기서의 제약사항은 수열의 길이이다. 이 길이를 1부터 하나씩 증가시켜면서 그 때의 최장 부분 수열의 길이를 구해보자.

• $N=1$일 때, 가장 긴 부분 수열은 10이므로 최장 길이는 1이 된다.
• $N=2$일 때, 가장 긴 부분 수열은 10, 20이므로 최장 길이는 2가 된다.
• $N=3$일 때, 가장 긴 부분 수열은 10, 20이므로 최장 길이는 2이다.
• $N=4$일 때, 가장 긴 부분 수열은 10, 20, 30이므로 최장 길이는 3이다.
• $N=5$일 때, 가장 긴 부분 수열은 10, 20, 30이므로 최장 길이는 3이다.
• $N=6$일 때, 가장 긴 부분 수열은 10, 20, 30, 50이므로 최장 길이는 4이다.

여기서 중요한 것은 $N=k$ 때의 최장 길이는 $N=l (l ≤ k)$일 때의 최장 길이+1로 갱신된다는 점이다. 단, $k$번 째 수열의 숫자가 $l$번째 숫자보다 클 때만 해당된다. 즉, 만약 $k$번 째 숫자가 $l$번째 숫자보다 크면 최장 길이를 현재 값과 $N=l$일 때의 최장 길이+1로 갱신하고, 만약 작다면 현재값을 유지한다.

결론

제약사항은 수열의 길이이고 구하고자 하는 것은 최장 길이의 최대값이므로 이를 점화식으로 나타내면 다음과 같다.

• $table[i]$ : 수열의 길이가 i번째까지 일 때의 최장 부분 수열의 길이
• $j$ : i보다 작고 0보다 크거나 같은 정수

교훈

보통 다이나믹 프로그래밍의 문제에서 입력값(ex. 수열의 길이)이 테이블의 행과 열이 되고 구하고자 하는 값(ex. 최장 부분 수열 길이)가 테이블을 채우는 값이 된다.

소스코드

import sys


n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
table = [1] * (n)

for i in range(n):
  for j in range(i):
    # i번째 수가 j번째 수보다 클 때만 갱신
    if nums[j] < nums[i]:
        table[i] = max(table[i], table[j]+1)

print(max(table))