백준: 11053 가장 긴 증가하는 부분 수열

문제

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

 

문제 풀이

 예시의 수열 10 20 10 30 20 50은 다음과 같이 가장 긴 증가하는 부분 수열을 찾을 수 있다. 앞의 수열에서 작은 수가  있는지 카운트하여, 각 값에 따라 증가하는 부분수열의 길이를 찾을 수 있다.

 

20 보다 작은 수가 있는가?

수열	10	20	10	30	20	50
카운트	1	2	1	1	1	1

• 10은 20 보다 작으므로 10의 카운트 값에서 + 1한 값을 20의 카운트로 변경

10 보다 작은 수가 있는가?

수열	10	20	10	30	20	50
카운트	1	2	1	1	1	1

• 10보다 작은 수가 없으므로 변경하지 않음

30 보다 작은 수가 있는가?

수열	10	20	10	30	20	50
카운트	1	2	1	3	1	1

• 작은 수 중, 카운트가 가장 큰 값에 + 1한 값을 30의 카운트로 변경

20 보다 작은 수가 있는가?

수열	10	20	10	30	20	50
카운트	1	2	1	3	2	1

• 첫번째와 마찬가지로 10 밖에 없으므로 2로 카운트를 변경함

50 보다 작은 수가 있는가?

수열	10	20	10	30	20	50
카운트	1	2	1	3	2	4

• 작은 수 중 30의 카운트가 가장 크므로 해당 카운트 값 + 1을 50의 카운트로 변경함

 여기서 계산된 카운트는 증가하는 부분 수열의 길이가 된다. 또한 수열의 첫번째 값은 자기자신을 제외하고 비교 대상이 없고, 모든 수열은 자기 자신을 경우에 수에 포함하므로 초기에 1로 초기화 해주면 된다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))
    # 자기자신은 포함하므로 1로 초기화
    answer = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                answer[i] = max(answer[i], answer[j] + 1)
    print(max(answer))