링크

https://leetcode.com/problems/k-inverse-pairs-array/?envType=daily-question&envId=2024-01-27

문제

문제 설명 및 요점

• Inverse Pair는 인덱스는 증가하지만 값은 감소하는 형태의 숫자 쌍을 뜻한다.
• 1~ $n$ 까지의 숫자가 있을 때, $k$ 의 Inverse Pair 를 갖는 숫자 배치 경우의 수를 찾아야 한다.
• 정답이 클 수 있으니 $10^9 + 7$ 로 나눈 나머지를 반환한다.

풀이

• 조합론에서의 오일러 수 개념을 확장한 문제. 오일러 수는 연속되는 인덱스에서 감소하는 쌍에 해당하는 순열이고, 문제에서는 인덱스의 연속 조건이 빠져있다.

• 그래도 오일러 수 보다는 점화식 찾기가 쉬운 편이지만, 그럼에도 너무 어렵다…

• 각 $n$ 에 대해, $k$ 는 $_nC_2$ 까지 존재할 수 있다.

  • Inverse Pair가 가장 많이 존재할 수 있는 경우를 생각해보자.
  • 완벽하게 내림차순으로 정렬 되었을 때: [n, n-1, ..., 2, 1]
  • 위 경우에서 Inverse Pair는 $n$ 개의 숫자에서 2개의 숫자를 순서 고려 없이 뽑은 경우의 수와 같다.

• 또한, 각 $n$ 에 대해 모든 $k$ 를 합치면 $n!$이 나온다. ( $n$개의 숫자를 나열하는 경우의 수)

• $n=2$ 에서 출발해보자. [1,2] ( $k=0$ )와 [2,1]( $k=1$ ) 두 경우가 존재한다.

• $n=3$ 일 때, $0 \le k \le 3$ 이다. $k=0$ 일 때는 항상 1이므로, 나머지 경우에 대해 생각해보자.

  • $k=1$ 인 경우, [1,2] $(n=2,k=0)$ 인 경우에서 3을 중간에 끼워 넣거나, [2,1] $(n=2,k=1)$ 인 경우에서 3을 맨 뒤에 끼워 넣는 경우 밖에 없다.
  • $k=2$인 경우, [1,2] $(n=2,k=0)$ 인 경우에서 3을 맨 앞에 끼워 넣거나, [2,1] $(n=2,k=1)$ 인 경우에서 3을 중간에 끼워 넣는 경우 밖에 없다.
  • $k=3$인 경우, [2,1] $(n=2,k=1)$ 인 경우에서 3을 맨 앞에 끼워 넣는 경우 밖에 없다.

• $n=2$ -> $n=3$ 을 만드는 원리가 보이는가? $n=2$ 인 경우의 수에서 3을 어떻게 끼우느냐에 달려있다.

  • 표기를 간소화하기 위해 $(n,k)$ 형태로 표기하겠다.
  • $(2,0)$ 은 $(3, 0), (3, 1), (3, 2)$에 관여한다.
  • $(2,1)$ 은 $(3, 1), (3, 2), (3, 3)$에 관여한다.
  • 시각화 하면 이와 같다.

• $n=3$ -> $n=4$ 도 만들어보자. $n=3$ 인 경우의 수에서 4를 어떻게 끼울지 생각해보면 아래와 같은 결과를 얻을 수 있다.

  • 표기를 간소화하기 위해 $(n,k)$ 형태로 표기하겠다.
  • $(3, 0)$은 $(4, 0), (4, 1), (4, 2), (4, 3)$에 관여한다.
  • $(3, 1)$은 $(4, 1), (4, 2), (4, 3), (4, 4)$에 관여한다.
  • $(3, 2)$은 $(4, 2), (4, 3), (4, 4), (4, 5)$에 관여한다.
  • $(3, 3)$은 $(4, 3), (4, 4), (4, 5), (4, 6)$에 관여한다.
  • 시각화 하면 이와 같다.

• 수열이 만들어지는 원리는 이게 다인데, 이걸 그대로 구현하면 시간초과가 발생한다. $n$ 개의 숫자에 대해 $k$ 개의 숫자를 다음 수열에 $n+1$ 번 누적시켜줘야 하므로, $O(N^2K)$ 라서 해결할 수 없다.

• 따라서 계산을 최적화해야 한다. 다시 위 시각화를 끌고 와서 생각해보자.

  • 표기를 간소화하기 위해 $(n,k)$ 형태로 표기하겠다.
  • $(4,2)$ 가 어떻게 만들어지는지 자세히 살펴보자.
  • $(4,2)$ 는 빨간 직선 하나, 초록 직선 하나, 파란 직선 하나로 구성되어 있다.
  • $(4,1)$ 은 빨간 직선 하나, 초록 직선 하나로 구성되어 있다.
  • 따라서 $(4,2) = (3, 0) + (3, 1) + (3, 2) = (4, 1) + (3, 2)$ 이다.
  • 마치 조합의 성질 처럼, $(n, k) = (n, k -1) + (n - 1, k)$ 를 통해 계산을 최적화 할 수 있다.
  • 다만, 이는 $k < n$ 인 경우에만 성립한다. 나머지는 대칭성을 이용해 계산해야 한다.
  • $(4,3), (4,4)$ 에 집중해보자.
  • $(4,3)$ 은 빨강, 초록, 파랑, 노랑으로 구성되어 있다.
  • $(4,4)$ 는 초록, 파랑, 노랑으로 구성되어 있다.
  • 따라서 $(4, 4) = (4,3) + (3, 4) - (3, 0)$ 이다.
  • 나머지 경우도 확장해보면, $k \ge n$ 인 경우에 대해 $(n, k) = (n , k - 1) + (n - 1, k) - (n - 1, k-n)$ 이 성립함을 알 수 있다.

• 정리하면, 최종 점화식은 다음과 같다.

  • 표기를 간소화하기 위해 $(n,k)$ 형태로 표기하겠다. $n \ge 2$ 에서
  • $k < n$ 인 경우에 대해, $(n, k) = (n, k -1) + (n - 1, k)$
  • $k \ge n$ 인 경우에 대해, $(n, k) = (n , k - 1) + (n - 1, k) - (n - 1, k-n)$
  • 점화식을 그대로 재귀로 구현해도 정답을 받을 수 있다.
  • 생 재귀로는 당연히 불가능하고, 이전 값을 저장해두어야 한다. 파이썬의 경우 @cache 데코레이터를 사용하면 쉽게 구현할 수 있다.

• 좀 더 최적화를 시켜보자.

  • $n=1$ 일 때 부터 시작한다. $(1, 0)$ 은 1이다.
  • $k + 1$ 칸 짜리 배열을 하나 준비하고, 빈 배열과 이전 값을 누적할 변수를 하나 둔다.
  • 누적값을 빈 배열에 계속 추가해 나가다가, $k \ge n + 1$ 이 되는 시점부터 누적값에서 dp[k - n - 1] 을 뺀다.
  • $_nC_2$ 를 전부 계산할 필요 없이, $k$까지만 계산한 후 dp 배열과 교체해준다.
  • 코드로 옮기면 아래와 같다. $10^9 + 7$ 과의 나머지 연산을 잊지 말자.

코드

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10 ** 9 + 7
        dp = [0] * (k + 1)
        dp[0] = 1
        
        for i in range(n):
            temp, number = [], 0
            for j in range(k + 1):
                number += dp[j]
                if j-i >= 1: number -= dp[j-i-1]
                number %= MOD
                temp.append(number)
            dp = temp
        return dp[k]