[LeetCode] 629. K Inverse Pairs Array
LastMod:
👨💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)
링크
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을 맨 앞에 끼워 넣는 경우 밖에 없다.
- \( k=1 \) 인 경우,
- \( 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]
Leave a comment