[백준 알고리즘/Python] 11053 가장 긴 증가하는 부분 수열

문제

 

 

문제이해

수열이 주어지면 각 자리수마다 따로 생각해봅니다. 왼쪽으로 더 적은 수가 들어오면 그것이 수열이 됩니다.

처음에 이해가 되지 않아 https://bitwise.tistory.com/215 블로그를 참고했습니다.

 

코드

test_case = int(input())
nums = list(map(int,input().split()))

dp = [1] * test_case

for i in range(1, test_case):
    for j in range(i): # 자리수 맨 왼쪽부터 들어온다.
        if(nums[i] > nums[j]): # 자리수 왼쪽부터 체크
            dp[i] = max(dp[j]+ 1 , dp[i]) # 바뀐 것, 더 큰것 체크

print(max(dp)) # 꼭 끝쪽에 최대 길이 배열이 없을 수 있다.

모든 수열은 자기자신을 포함할 수 있기 때문에 1의 길이를 가집니다.

 

dp는 수열의 개수를 의미합니다.

 

수열을 for문에 돌릴 건데 자기 차례가 되면 이전의 수열을 체크해봅니다. 나보다 더 작은 수들이 있는지

체크해서 있다면 나보다 더 작은수의 수열 개수의 +1을 하면 됩니다. 자기 자신의 이전수열 모두를 체크해봐야죠

그리고 수열이 맨 끝자리에서만 최대길이가 나오지는 않습니다.

 

ex)

{10, 20, 30, 20, 10} 인 경우에 30에서 최대길이가 나옵니다.

그래서 수열의 개수중 가장 큰값을 구하면 됩니다.