예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력 1
6 10 20 10 30 20 50
예제 출력 1
4
LIS는 Longest Increasing Subsequence 로써 최장증가부분수열 문제이다.
주어진 입력이
10
1 5 2 8 7 3 4 6 9 10
라고 하자
답은 1,2,3,4,6,9,10로 7이다.
가장 긴 수열을 찾으려면 자신의 숫자에서 이전 숫자들 다음 숫자이면 이전 숫자에 표기를 하고 현재 숫자에 다음 표기를 해주면 된다.
dp=[0]*11 을 만들어보자
1. 1에서 이전 숫자가 없으니
dp[1]은 1이다.
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2. 5에서 이전 숫자 1이 있으니
dp[5]=dp[1]+1=2가 되며 1,5는 증가하는 수열이다.
[0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0]
3. 2에서 이전 숫자들중에 자기보다 작은 수는 1이므로
dp[2]=dp[1]+1=2가 되며 1,2는 증가하는 수열이다.
[0, 1, 2, 0, 0, 2, 0, 0, 0, 0, 0]
4. 8에서 이전 숫자들 중에 자기보다 작은 수는 2 또는 5가 있다.
dp[8]=max(dp[:8])+1=3 이다. 즉, 자기 이전 숫자중 가장 연속인거에 자기를 카운트하면된다.
[0, 1, 2, 0, 0, 2, 0, 0, 3, 0, 0]
5. 7도 마찬가지로 dp[7]=max(dp[:7])+1=3이다.
[0, 1, 2, 0, 0, 2, 0, 3, 3, 0, 0]
6. 3도 마찬가지로 dp[3]=max(dp[:3])+1=3이다.
[0, 1, 2, 3, 0, 2, 0, 3, 3, 0, 0]
마지막은
dp[10]=max(dp[:10])+1=7이 된다.
[0, 1, 2, 3, 4, 2, 5, 3, 3, 6, 7]
즉, 자기 번호에서 이전 번호 보다 큼을 표기하면된다.
정답 코드
import sys
input=sys.stdin.readline
if __name__=="__main__":
N=int(input())
infos=list(map(int, input().split()))
dp=[0]*1001
for i in infos:
dp[i]=max(dp[:i])+1
print(max(dp))
