프로그래머스 타겟 넘버 정답 코드

난이도 ★★★☆☆

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

반복문이 아닌 재귀로 풀었습니다. f(i, t) = f(i + 1, t + n[i]) + f(i + 1, t - n[i])   동적계획법(Dynamic Programming)도 사용하였는데, 이부분은 성능을 위한 것이므로 없어도 결과에는 영향이 없습니다. (헷갈릴시 cache 변수를 제거하시면 됩니다)

 

 

 

이하는 코드입니다.

import java.util.HashMap;
import java.util.Map;
 
public class Solution {
    private Map<Integer, Integer>[] cache; // Dynamic Programming
    private int[] numbers;
 
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        cache = new HashMap[numbers.length]; // TODO Remove the warning
 
        for (int i = 0; i < numbers.length; i++) {
            cache[i] = new HashMap<>();
        }
 
        int answer = getCount(0, target);
        return answer;
    }
 
    // f(i, t) = f(i + 1, t + n[i]) + f(i + 1, t - n[i])
    private int getCount(int startIdx, int target) {
        if (startIdx >= numbers.length) {
            return 0;
        }
 
        if (startIdx == numbers.length - 1) {
            if (numbers[startIdx] == target || numbers[startIdx] == target * -1) { // Don't forget -1
                return 1;
            } else {
                return 0;
            }
        }
 
        Integer count = cache[startIdx].get(target);
 
        if (count != null) {
            return count;
        }
 
        count = getCount(startIdx + 1, target + numbers[startIdx]) + getCount(startIdx + 1, target - numbers[startIdx]);
        cache[startIdx].put(target, count);
 
        return count;
    }
}