November 24, 2020
BOJ 11053번 : 가장 긴 증가하는 부분 수열
의 길이를 가진 수열이 있을 때 가장 긴 부분 수열의 길이를 구하는 문제이다.
문제의 예시인 10, 20, 10, 30, 20, 50
을 가지고 생각해보자. 여기서의 제약사항은 수열의 길이이다. 이 길이를 1부터 하나씩 증가시켜면서 그 때의 최장 부분 수열의 길이를 구해보자.
10
이므로 최장 길이는 1이 된다.10, 20
이므로 최장 길이는 2가 된다.10, 20
이므로 최장 길이는 2이다.10, 20, 30
이므로 최장 길이는 3이다.10, 20, 30
이므로 최장 길이는 3이다.10, 20, 30, 50
이므로 최장 길이는 4이다.여기서 중요한 것은 때의 최장 길이는 일 때의 최장 길이+1로 갱신된다는 점이다. 단, 번 째 수열의 숫자가 번째 숫자보다 클 때만 해당된다. 즉, 만약 번 째 숫자가 번째 숫자보다 크면 최장 길이를 현재 값과 일 때의 최장 길이+1로 갱신하고, 만약 작다면 현재값을 유지한다.
제약사항은 수열의 길이이고 구하고자 하는 것은 최장 길이의 최대값이므로 이를 점화식으로 나타내면 다음과 같다.
보통 다이나믹 프로그래밍의 문제에서 입력값(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))