오답 여부: o
편집 시간: 2022년 3월 14일 오후 1:21
코드
Algorithm/11053.py at main · Junroot/Algorithm
Algorithm/11053-2.py at main · Junroot/Algorithm
풀이
느린 풀이
처음에는 함수 f(index, current_number)를 만들어 점화식을 만들었다.
- f(index, current_number): 수열 A의 index부터 n - 1번째 까지 중에서 current_number보다 큰 수들로 이루어진 부분 수열의 최대 길이
a[index] > current_number 인 경우: f(index, current_number) = max( 1 + f(index+1, a[index]), f(index+1, current_number) )
a[index] ≤ current_number 인 경우: f(index, current_number = f(index+1, current_number)
이런 점화식을 만들고 dp를 사용하면 시간 제한에 아슬하게 통과한다. 원인을 분석하자면 dp의 파라미터가 (index, current_number) 두 가지가 있기 때문에 값을 재활용할 수 있을 확률이 줄어든다.
빠른 풀이
다른 사람의 풀이를 보니 부분 문제로 만들어 이를 활용하는 방법을 사용했다.
- f(index): 수열의 0부터 index 까지 중에서 가장 긴 부분 수열의 길이
f(n) = max(f(k) + 1, 1) | {k| a[k] < a[index], 1 ≤ k ≤ n}