가장 긴 증가하는 부분 수열 (1) 썸네일형 리스트형 [BOJ][DP] 11053. 가장 긴 증가하는 부분 수열 문제 -> https://www.acmicpc.net/problem/11053 오래 생각을 해도 기존에 했던 생각밖에 들지 않고참신한 방법이 들지 않는다. 결국 또 참고하게 됬다..무엇이 문제일까. ============================================= DP에서 유명한 문제라고 한다. 일일이 내 뒤에있는 값을 신경쓰며 비교하고 지지고 볶고 할 필요 없이, 현재 자기 자신보다 작은 값이 가지고 있는 길이(dp값) 중 제일 큰 것을 자신을 포함해서 더하면 된다. 처음에는 모두 0이다.첫번째 값인 10은 자기 자신밖에 없으므로 1. 두번째 20은 자기 앞에 자기보다 작은 수인 10이 존재한다.고로 그 10의 길이인 1을 더한다. 세번째 10은 자기보다 작은 수가 없어 그냥 자기 길이.. 이전 1 다음
