2023.05.14 Today's Challenge

fabichoi 2023. 5. 14. 23:45

https://leetcode.com/problems/maximize-score-after-n-operations/

Maximize Score After N Operations - LeetCode

Can you solve this real interview question? Maximize Score After N Operations - You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array. In the ith operation (1-indexed), you will: * Choose two elements,

leetcode.com

꽤 복잡한 문제였음

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        max_states = 1 << len(nums)
        final_mask = max_states - 1

        dp = [0] * max_states

        for state in range(final_mask, -1, -1):
            if state == final_mask:
                dp[state] = 0
                continue
            
            numbers_taken = bin(state).count('1')
            pairs_formed = numbers_taken // 2

            if numbers_taken % 2:
                continue
            
            for fi in range(len(nums)):
                for si in range(fi+1, len(nums)):
                    if (state >> fi & 1) == 1 or (state >> si & 1) == 1:
                        continue
                    current_score = (pairs_formed+1) * math.gcd(nums[fi], nums[si])
                    state_after_picking_curr_pair = state | (1 << fi) | (1 << si)
                    remaining_score = dp[state_after_picking_curr_pair]
                    dp[state] = max(dp[state], current_score + remaining_score)
        
        return dp[0]