[Python] 백준(BOJ) 11053번 - 가장 긴 증가하는 부분 수열

링크

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

난이도(solved.ac 참고)

실버2

풀이

응용이 많이 되는 유형이다. 이 문제를 먼저 접한 이유는 원래 오늘 풀기로 했던 병사 배치하기를 풀 때 필요한 부분이라고 생각되었기 때문이다. 

n까지의 범위를 가지는 i와 i까지의 범위를 가지는 j를 돌면서, 증가하는 부분 수열의 길이가 증가하려면 a[i]의 값이 a[j]보다 커야한다. 이 경우 dp의 값은 더 작은 인덱스인 j의 dp 인덱스에 1을 더해준 것과, 기존의 dp[i]의 값중에 더 큰 값이 들어가야 한다. 전자에서 +1이 들어가는 이유는 증가하는 부분수열의 길이가 1 증가했기 때문이다.