[Leetcode] 629. K Inverse Pairs Array
문제 : https://leetcode.com/problems/k-inverse-pairs-array/
inverse pairs : 0 <= i < j < nums.length and nums[i] > nums[j] 조건을 만족하는 [i, j].
DP[n][k] = n 크기의 nums 배열이 있을 때 k 개의 inverse pairs 를 가지는 경우의 수.
n-1 크기의 nums에서 어떻게 n 크기의 nums를 만들 수 있는지 먼저 살펴보자.
[그림 1] 에서 n=4, k=1인 경우는 왼쪽 아래와 같이 총 3가지 방법이 있다.
3가지 리스트들에서 4인 원소들을 제거하면 오른쪽과 같은 리스트들이 나온다.
여기에서 추론 가능한건 n-1 크기의 배열에서 추가되는 4의 위치에 따라 k(inverse pairs)의 크기가 달라진다는 것이다.
예를 들어보자. [그림 2] 에서 [2, 1, 3] 리스트에서 뒤에서 두 번째 위치에 4를 넣어 [2, 4, 1, 3] 리스트를 만들어보자.
기존 리스트([2,1,3])의 inverse pairs는 1이다. 새로 추가되는 4는 가장 큰 수이기 때문에 4 뒤에 있는 원소들의 수만큼 inverse pairs들이 생긴다. [그림 2] 에서는 [4, 1], [4, 3] 이 추가되어 총 3이 되는걸 확인할 수 있다.
즉, dp[n][k] 리스트들에서 n+1 원소를 추가할 때 어디 위치에 추가하냐에 따라서 k가 달라진다.
예를 들어, 뒤에서 4번째 위치에 원소를 추가한다면 dp[n+1][k+4]에 dp[n][k]를 더해주어야 한다는 뜻이된다.
기본 아이디어는 위와 같고, DP를 어떻게 채우는지는 https://leetcode.com/problems/k-inverse-pairs-array/discuss/2293243/DP-algo-explained-with-figures-Python 링크 참조.
시간/공간복잡도는 O(NK)
까먹기 전에 아이디어만 간단히. 역시 DP 난이도가 천차만별이구만. DP 문제인걸 알아도 점화식 생각해내는데 시간이 오래걸렸다.