368. Largest Divisible Subset

[zeikar]

Problem link

https://leetcode.com/problems/largest-divisible-subset

Problem Summary

리스트가 주어질 때 모든 subset이 각각의 배수가 되도록 하는 최대 길이의 subset을 구하는 문제.

Solution

일단 순서가 중요하지 않으므로 정렬을 먼저 하자.

그러면 뭔가 보이는데 두 인덱스를 i, j (i < j) 라 했을 때 nums[j] % nums[i] == 0이면 뒤로 이어 붙일 수 있다. 이런식으로 모든 원소에 대해 길다면 이어 붙이는 식으로 이어 나갈 수 있다.
LIS (Longest Increasing Subsequence) 문제와 유사하다.

구현은 간단하게 O(n^2) Top Down DP로 해봤는데 메모리도 O(n^2) 먹어서... (크지는 않지만) 메모리도 O(n) 하려면 길이 배열과 parent 배열을 둘다 저장하면 가능하다.
구현이 쉽기 위해 앞에 더미로 1을 더 집어넣었다. (가장 긴 리스트가 0번부터 시작하지 않을 수 있기 때문)

Source Code

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        nums = [1] + nums

        @cache
        def countMultiples(i):
            res = []
            for j in range(i + 1, len(nums)):
                c = countMultiples(j)
                if nums[j] % nums[i] == 0 and len(res) <= len(c):                     
                    res = c

            return [nums[i]] + res


        return countMultiples(0)[1:]