leetcode 494. Target Sum 풀이

문제 : int 로 이루어진 list가 주어질때 원소들의 +, - 를 통해 target에 도달하는 경우의 수를 반환하라.

Follow up :

 

아이디어 : DFS 를 통해 풀었지만 풀면서도 이거 반드시 timeout 날 것이라 생각했고 역시나 timeout이 발생했다. dictionary 를 통해서 tracking을 해야할거 같은데 명확한 방법이 생각나지 않았다.

 

코드 :

 처음 작성한 코드

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        global ans
        ans = 0
        def dfs(i, s):
            global ans
            print(i, s, ans)
            if i == len(nums) - 1:
                if s == target:
                    ans += 1
                return
            else:
                dfs(i+1, s+nums[i+1])
                dfs(i+1, s-nums[i+1])
        dfs(0, nums[0])
        dfs(0, -nums[0])
        return ans

nums의 길이가 최대 20이기 때문에 2^20을 하다보면 당연히 timeout이 발생한다

 

풀이를 보고 작성한 코드

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.m = {}
        return self.dp(nums, len(nums)-1, 0, target)
    def dp(self, nums, i, s, target):
        if (i, s) in self.m:
            return self.m[(i, s)]
        if i < 0:
            if s == target:
                return 1
            else:
                return 0
        else:
            p = self.dp(nums, i-1, s + nums[i], target)
            n = self.dp(nums, i-1, s - nums[i], target)
        self.m[(i, s)] = p + n
        return self.m[(i, s)]

거의 비슷한 포인트로 풀었지만 딕셔너리의 index에 순회중인 index와 current sum을 튜플로 설정하여 저장한다.

딕셔너리의 활용법에 대해 좀 더 생각하면 충분히 풀었을거같은데 아쉽다.

 

학습 포인트 : 위와 같이 딕셔너리의 인덱스를 좀 더 넓게 생각하여, 튜플로도 사용 가능하면 활용할 방법이 많을 것이다. 또한 dp 문제가 주어졌을 때

• 0/1 Knapsack
• Unbounded Knapsack
• Shortest Path (eg: Unique Paths I/II)
• Fibonacci Sequence (eg: House Thief, Jump Game)
• Longest Common Substring/Subsequeunce

위의 5가지의 frame을 먼저 생각해서 문제를 푼다면 더욱 쉽게 접근할 수 있을 것이다.

시간이 된다면 MIT의 DP 강의도 들어보면 좋을것이다.

출처 : leetcode.com/problems/target-sum/