Google 태그 관리자 아이콘

알고리즘 풀이

.leetcode(494. Target Sum)

silvergoni 2021. 2. 12. 10:51
반응형

문제

https://leetcode.com/problems/target-sum/

문제 풀기 전

  1. 2^n의 경우의 수를 줄여야한다.
  2. 큰수의 구성요소 찾던 완전제곱수 문제가 생각난다.
  3. 전체 숫자합에서 주어진 결과를 뺀 값은 여기내부의 숫자로 구성된다. 그 구성의 숫자를 구하면 되지 않을까. 아니다..
  4. 며칠전에 푼 Path sum으로 풀면 되지 않을까. 공간도 많이쓰고 빠르지도 않을거 같다.
  5. 전체합과 누적 수를 뺀값을 갖고 있으면서 그걸 저장해서 풀자.

직접 푼 풀이

소요시간: 15분(09:45 ~ 10:00)

class Solution {
    private int[] numbers;
    private int goal;
    private int[][] cache;
    public int findTargetSumWays(int[] nums, int S) {
        numbers = nums;
        goal = S;
        int total = 0;

        cache = new int[nums.length][2001];
        for (int i=0; i<nums.length; i++) {
            for (int j=0; j<2001; j++) {
                cache[i][j] = -1;
            }
        }

        for(int num: nums) {
            total += num;
        }

        return solve(0, S, total);
    }

    private int solve(int index, int sum, int total) {
        if (index == numbers.length) {
            if (sum == 0) {
                return 1;
            }
            return 0;
        }
        if (sum > total) {
            return 0;
        }

        if (cache[index][sum+1000] != -1) {
            return cache[index][sum+1000];
        }


        int ret = 0;
        ret += solve(index+1, sum-numbers[index], total-numbers[index]);
        ret += solve(index+1, sum+numbers[index], total-numbers[index]);

        return cache[index][sum+1000] = ret;
    }

}

느낀점

  1. 흔히 memoization이라 불리는 기법이다. 리턴한 값을 기억해두고 다음에 다시 같은 파라미터가 넘어올때 저장된 값으로 대체하는 방법이다.
  2. dynamic programming으로도 풀 수 있다.
  3. dp로 풀면 O(n)정도의 공간과 속도가 나온다고 할 수 있다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[][] dp = new int[nums.length][2001];

        dp[0][1000 - nums[0]] = 1;
        dp[0][1000 + nums[0]] += 1;

        for (int i=1; i<nums.length; i++) {
            for (int j=0; j<2001; j++) {
                if (dp[i-1][j] > 0) {                 
                    dp[i][j+nums[i]] += dp[i-1][j]; 
                    dp[i][j-nums[i]] += dp[i-1][j];
                }
            }
        }

        return S > 1000 ? 0 : dp[nums.length-1][1000+S];
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)