[hard] 629. K Inverse Pairs Array

문제

https://leetcode.com/problems/k-inverse-pairs-array/

K Inverse Pairs Array - LeetCode

---

풀이방법

숫자제한을 보니 제일 먼저 떠오르는 브루트포스로 풀면 시간초과가 날 수 밖에 없는 문제라서 DP로 접근해야겠다고 생각했다

그런데 DP 규칙을 어떻게 만들어야하는지... 역시 hard...

그래서 https://leetcode.com/problems/k-inverse-pairs-array/discuss/1282998/Python%3A-Explained-Bottom-Up-DP 참고했다

"j >= i, along with doing dp[i][j] = dp[i-1][j] + dp[i][j-1] we also subtract dp[i-1][j-i] for the invalid shifting case" 이 부분이 사실 아직도 잘 이해가 안간다...

반응형

---

코드

### DP ###
class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        dp = [[0]*(k+1) for _ in range(n+1)]
        
        for i in range(1,n+1):
            dp[i][0] = 1
            
        for i in range(1,n+1):
            for j in range(1,k+1):
                if i==1 and j==1:
                    continue
                elif j > i*(i-1)//2:
                    dp[i][j] = 0
                elif j == i*(i-1)//2:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                    if j >= i:
                        dp[i][j] -= dp[i-1][j-i]
        
        return dp[n][k] % (10**9 + 7)

### 브루트포스: 시간초과 ###
class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        
        def dfs(curarr,revcnt):
            if revcnt > k:
                return 0
            if len(curarr) == n:
                if revcnt == k:
                    return 1
                else:
                    return 0
                
            result = 0
            for i in range(1,n+1):
                flag = True
                newrevcnt = revcnt
                for j in curarr:
                    if i == j:
                        flag = False
                        break
                    elif j > i:
                        newrevcnt += 1
                if flag:
                    result += dfs(curarr[:]+[i],newrevcnt)
                    
            return result

		return dfs([],0) % (10**9 + 7)