[알고리즘] 백준 11722번
문제
https://www.acmicpc.net/problem/11722
풀이
오늘은 가장 긴 감소하는 부분 수열 문제를 풀어보았습니다. 유명한 dp 문제의 유형 중 하나이고 난이도 역시 쉽다고 하는데 저는..역시나 아직은 알고리즘이 약해서 그런지 여러 블로그에서 힌트를 얻어 풀었습니다.
주어진 수열에서 가장 긴 감소하는 부분 수열을 구하기 위해서는 수열의 각 요소를 기준점으로 이전의 요소들과 비교를 해서 본인보다 큰 요소가 존재한다면 자신의 길이를 1 추가하는 방식으로 접근하였습니다.
그렇게 되면 이전 요소들 또한 각각 부분 수열에 포함되어 있는데 해당 부분 수열에 속해서 더 긴 감소하는 부분 수열을 이룰수 있다면 그곳에 속하는 코드를 작성해주어야 합니다. 코드는 다음과 같습니다.