반응형
문제
https://leetcode.com/problems/target-sum/
문제 풀기 전
- 2^n의 경우의 수를 줄여야한다.
- 큰수의 구성요소 찾던 완전제곱수 문제가 생각난다.
- 전체 숫자합에서 주어진 결과를 뺀 값은 여기내부의 숫자로 구성된다. 그 구성의 숫자를 구하면 되지 않을까. 아니다..
- 며칠전에 푼 Path sum으로 풀면 되지 않을까. 공간도 많이쓰고 빠르지도 않을거 같다.
- 전체합과 누적 수를 뺀값을 갖고 있으면서 그걸 저장해서 풀자.
직접 푼 풀이
소요시간: 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;
}
}
느낀점
- 흔히 memoization이라 불리는 기법이다. 리턴한 값을 기억해두고 다음에 다시 같은 파라미터가 넘어올때 저장된 값으로 대체하는 방법이다.
- dynamic programming으로도 풀 수 있다.
- 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];
}
}
누적되는 알고리즘 접근 설명서
'알고리즘 풀이' 카테고리의 다른 글
.leetcode(416. Partition Equal Subset Sum) (0) | 2021.02.14 |
---|---|
.leetcode(438. Find All Anagrams in a String) (0) | 2021.02.14 |
.leetcode(253. Meeting Rooms II) (0) | 2021.02.07 |
.leetcode(437. Path Sum III) (0) | 2021.02.06 |
.leetcode(309. Best Time to Buy and Sell Stock with Cooldown) (0) | 2021.02.05 |