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

https://www.acmicpc.net/problem/11053

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

 

소스코드

 

 

 

 

풀이

다이나믹 프로그래밍 DP로 푸는 문제입니다 !

 

주어진 수열에 대해 증가하는 부분 수열을 작성하고, 부분 수열의 길이가 가장 긴 것들을 적어보면 다음과 같습니다. 

 

 

이 때, 수열 중 첫 숫자인 10은 만들 수 있는 수열이 자기 자신 밖에 없기 때문에 길이가 1이 되고, 변수 length에는 1이 저장됩니다. 

그 다음 수인 20은 그 전 수인 10과 비교해봤을 때 크고, 만들 수 있는 증가하는 부분 수열의 길이 또한 2로 10보다 더 큽니다. 이 때 변수 length에는 +1이 되게 되는데, 그 이유는 부분 수열 길이를 비교해보면 알 수 있습니다. 

 

이러한 방식이 계속해서 반복되고 수열 중 가장 큰 수가 있는 곳에서 증가하는 부분 수열의 길이를 가장 크게 만들 수 있는 것을 확인할 수 있습니다 ! 

 

for j in range(i-1,0,-1): 구문은 수열안에 있는 수는 i인 수보다 인덱스가 1작은 수부터, 제일 처음 숫자까지 -1씩 적어지면서 수를 비교해줘야 합니다. 그래야만, 부분 수열을 만들 수 있는 지와, 부분 수열의 길이를 비교할 수 있기 때문입니다 !