[BOJ][DP] 11053. 가장 긴 증가하는 부분 수열

문제 -> https://www.acmicpc.net/problem/11053

오래 생각을 해도 기존에 했던 생각밖에 들지 않고

참신한 방법이 들지 않는다. 

결국 또 참고하게 됬다..

무엇이 문제일까.

=============================================

DP에서 유명한 문제라고 한다.

일일이 내 뒤에있는 값을 신경쓰며 비교하고 지지고 볶고 할 필요 없이,

현재 자기 자신보다 작은 값이 가지고 있는 길이(dp값) 중 제일 큰 것을 자신을 포함해서 더하면 된다.

처음에는 모두 0이다.

첫번째 값인 10은 자기 자신밖에 없으므로 1.

두번째 20은 자기 앞에 자기보다 작은 수인 10이 존재한다.

고로 그 10의 길이인 1을 더한다.

세번째 10은 자기보다 작은 수가 없어 그냥 자기 길이인 1만 넣어준다.

네번째 30은 자기보다 작은 수중에서 

가장 길이가 긴 두번째 20의 길이 값 2를 더한다.

다섯번째 20또한 자기보다 작은 10밖에 없으므로

1만 더한다.

마지막으로 50은 

자기보다 작은 수들 중에서 

가장 긴 길이값이 3이므로

3을 더한다.

이리하여 답이 4가 도출이 된다.

소스(Github)