[Algorithm] 프로그래머스_타겟 넘버

문제

numbers 배열에 n개의 음이 아닌 정수가 있습니다. 이 수를 더하거나 빼서 target과 같은 수를 만들려고 합니다. 이때 더하거나 빼서 target과 같은 수를 만들 수 있는 방법의 수를 return하면 되는 문제입니다.

풀이

target과 같은 수를 만들때는 dfs를 사용해서 풀이했습니다.
numbers의 0부터 dfs를 수행하고, numbers의 index를 하나씩 증가시켜가며 해당 인덱스의 값을 +/-로 변경 후 다시 넣어줍니다.
index의 값이 numbers의 길이와 같아지면, 전체 값을 더해 target과 동일해지는 경우만 세서 return 했습니다.

소스 코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    static int answer;

    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0);
        return answer;
    }

    public void dfs(int[] numbers, int target, int index) {
        if(index == numbers.length) {
            int sum =0;

            for(int num : numbers) {
                sum += num;
            }

            if(sum == target) {
                answer++;
            }
        } else {
            int num = numbers[index];

            numbers[index] = num * -1;
            dfs(numbers, target, index+1);

            numbers[index] = num;
            dfs(numbers, target, index+1);
        }
    }
}

후기

시뮬레이션 풀다가 갑자기 bfs/dfs가 그리워져서 풀었던 문제..
다들 뚝딱뚝딱 잘 푸시는 것 같습니다. 더 열심히 해야겠네요!