[리트코드] 494. Target Sum

494. Target Sum

문제

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

제한사항

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

풀이

프로그래머스 타겟넘버와 같은 문제이다. 하지만 백트래킹을 사용했을 때도 통과하는 프로그래머스와는 달리 leecode에서는 시간초과가 난다. 따라서 optimizing을 해줘야했다.

https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions.

위 글의 내용을 대충 정리해보자면 DP 문제를 만났을 때 어떻게 생각해야하는지에 대한 내용이다.

Category

DP 문제의 유형은 몇몇 카테고리로 좁혀지며 카테고리에 따라 사용해야하는 방식이 달라진다.

• 0/1 Knapsack : 물건 i를 선택하느냐 마느냐
• Unbounded Knapsack : 물건의 무게 총합이 w를 초과하지 않도록 선택하는 가격 총합의 최대치
• Shortest Path (eg: Unique Paths I/II)
• Fibonacci Sequence (eg: House Thief, Jump Game)
• Longest Common Substring/Subsequeunce

우리는 이 문제를 target에 도달하기 위해서 현재 숫자의 양수 값을 넣을지 음수 값을 넣을지 결정하는 문제로 바라 볼 수 있으므로 0/1 Knapsack 유형이다.

State

어떤 값을 트래킹해야할까? index와 현재 합이다.

index는 우리가 고려하고 있는 input의 subset을 나타낸다.

현재까지 합은 target에 도달했는지 아닌지 지금까지 진행 과정을 확인하기 위해 필요하다.

Decisions

각 분기에서 결정해야하는 것은 무엇일까?

1. 우리는 현재 값의 양수 값을 더해야한다.
2. 우리는 현재 값의 음수 값을 더해야한다.

BaseCase

재귀가 종료되는 조건은 input에 있는 모든 숫자를 사용했을 때이며, 이때 합이 target에 도달했는지 확인해야한다.

Code it

Optimize

재귀 함수의 오버헤드를 제거하기 위해서 sub problem을 한번만 해결해야한다. 이를 위해서 메모제이션을 사용한다.

결론은 dp배열을 이용해서 메모제이션하면 시간 초과를 줄일 수 있다.

이 문제를 dp라고 생각해본 적은 없었는데 dp로 해석하는 게 더 맞는 것 같다.

매번 계산을 새로하는 게 아니라 분기한 값을 dp 배열에 저장하고 저장되어 있는 이전 값을 가져다쓴다.

(index, 현재 합)을 키로 써야하기 때문에 딕셔너리로 dp 배열을 만든다.

class Solution:
    def tagetNums(self, nums, target, i, cur):
        if (i, cur) in self.memo:
            return self.memo[(i, cur)]
        if i == len(nums):
            return int(cur == target)
        
        cnt = 0
        cnt += self.tagetNums(nums, target, i + 1, cur + nums[i])
        cnt += self.tagetNums(nums, target, i + 1, cur - nums[i])
        
        self.memo[(i, cur)] = cnt
        return self.memo[(i, cur)]
    
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.memo = {} # dp 딕셔너리
        
        return self.tagetNums(nums, target, 0, 0)