알고리즘/동적프로그래밍

타겟넘버

e-pd 2020. 9. 6. 13:07

programmers.co.kr/learn/courses/30/lessons/43165?language=java

 

코딩테스트 연습 - 타겟 넘버

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+

programmers.co.kr

  1. 배열을 순회하면서 인덱스를 증가시킨다.
  2. 내부의 값이 타겟넘버와 동일하면 count증가
  3. 해당하는 값이 나올때까지, 재귀적으로 더하거나 뺀다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int solution(int[] numbers, int target) {
        return calculate(numbers, target, 0, 0);
    }
 
    private int calculate(int[] numbers, int target, int index, int num) {
        if (index == numbers.length) {
            return num == target ? 1 : 0;
        }
 
        return calculate(numbers, target, index + 1, num + numbers[index]) +
                calculate(numbers, target, index + 1, num - numbers[index]);
    }
}
 
cs