문제 파악
DP를 통해 일반적으로 해결하는 문제의 답은 총 개수나 최종적인 확률을 구하는 문제이다. k번째 해당하는 답의 실제 값을 구하는 것은 추가적인 처리가 필요하다. DP가 동작하는 과정에서 총 개수를 기록해놓고 k번째 값을 찾아나가는데 이 때 앞에서부터 하나씩 볼 경우 지나치게 많은 시간이 소요되므로 문제의 특성에 따라 한 번에 여러개 씩 점프하면서 탐색하는 방식을 사용하는 것이 좋다.
내가 생각한 풀이 방법은 먼저 해당 수열의 lis를 구한다. 그 뒤 해당 수열의 끝에서 부터 lis까지 몇 개의 증가 수열을 만들 수 있는지를 저장해 둔다. 끝에서 부터 저장하기 때문에 앞의 인덱스는 뒤에서 계산된 값을 활용해서 값을 채울 수 있다. 이렇게 끝까지 저장해 놓은 다음, 주어진 k번째 자리수를 찾는 것이다.
문제 풀이
먼저 개수를 세는 데에는 세 가지 조건을 활용한다. 증가 수열의 개수를 구하는 문제기 때문에 다음 인덱스의 값 중 현재 인덱스의 값보다 큰 값이어야 한다. 다음으로는 인덱스가 당연히 현재 인덱스보다 커야한다. 마지막으로 최장 증가 수열이 유지되려면 현재 인덱스의 lis보다 다음에 보려고 하는 인덱스의 lis가 1만큼 더 커야된다.
위 조건을 만족시키는 인덱스는 lis에 포함되는 인덱스라고 할 수 있다. 따라서 재귀적으로 해당 조건을 만족시키는 인덱스를 찾으면서 그 값을 합산해 위로 올려주면 된다. 이렇게 구한 총 개수를 인덱스 별로 캐쉬에 저장한다.
느낀점
지수적으로 증가하는 값의 오버플로우를 막기 위해 max와 INF활용, 알고리즘을 구현하기 전 확실한 설계 만들기
