문제 출처 : https://www.acmicpc.net/problem/11053
풀이 방법
A = {2, 54, 77, 21, 14, 32, 68} 로 주어졌다고 가정하고 찾을 수 있는 가장 긴 증가하는 부분 수열은 {2, 21, 32, 68} 혹은 {2, 14, 32, 68}로 길이는 4이다.
2는 첫 번째 숫자로 부분 수열의 길이가 무조건 1이다.
54는 그 앞에 54보다 작은 수가 2밖에 없고, 2의 부분 수열 길이는 1이었으므로 1을 더한 2가 부분 수열의 길이가 된다.
77은 그 앞에 77보다 작은 수가 2와 54가 있으며, 앞에 나온 부분 수열 길이 중 최대값은 2였으므로 2에 1을 더한 3이 부분 수열의 길이가 된다.
21은 그 앞에 21보다 작은 수가 2밖에 없고, 2의 부분 수열 길이는 1이었으므로 1을 더한 2가 부분 수열의 길이이다.이런 식으로 계속 숫자를 세어나간 후, 가장 긴 부분 수열의 길이를 구하기 위해 max(dp)를 출력한다.
소스 코드
Backend Developer