LeetCode - 368. Largest Divisible Subset (Python)

Medium, DP

RunTime : 213 ms / Memory : 16.95 MB

문제

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
If there are multiple solutions, return any of them.

풀이

• dp[i]를 각 nums[i]를 마지막 원소로하는 최대 크기의 부분집합의 크기로 지정.
• i > j에서 nums[i] % nums[j] == 0이라면, dp[i] = max(dp[j], dp[i] + 1)
• dp배열을 순회하면서 가장 큰 dp 값을 갖는 인덱스 (nums[i])를 추적
• prev 배열을 통해 가장 큰 부분집합의 마지막 원소부터 역순으로 추적
• 오름차순으로 리턴

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)       
        dp = [1] * n
        prev = [-1] * n

        max_idx = 0
        # 가장 큰 부분집합의 마지막 원소 인덱스

        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        prev[i] = j
            
            if dp[i] > dp[max_idx]:
                max_idx = i
        
        res = []
        while max_idx != -1:
            res.append(nums[max_idx])
            max_idx = prev[max_idx]
        
        return res[::-1]

dp는 어렵다...