[PROGRAMMERS] 타겟넘버(JAVA)

:D 문제

---

문제 설명

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

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

nubers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

Programmers

프로그래머스

 

 

:D 풀이 방법

---

나는 두가지 방법으로 문제를 풀었다.

첫번째는 연산자를 -(빼기)는 0, +(더하기)는 1로 표현하였다. 그리고 0과 1을 가지고 중복을 허용하는 N개의 수열을 만들었다.

만들어진 수열을 numbers에 수들과 연산하여 결과값이 target과 같다면, 카운트하여 해결했다.

 

두번째는 DFS를 적용해서 풀었다. 숫자배열, 타겟, 현재 인덱스, 연산 결과를 인자로 보내 각각 -(빼기)와 +(더하기)의 경우를 재귀 호출로 구현하였다. 

 

 

:D 작성 코드

---

첫번째 풀이 - 중복 순열

class Solution {
    
    static int N;
    static boolean[] isSelected;
    static int[] operators;
    static int[] numbers;
    static int target;
    static int answer;
    
    public int solution(int[] input, int t) {
        N = input.length;
        numbers = input;
        target = t;
        operators = new int[N];
        perm(0, 0);
        return answer;
    }
    
    public static void perm(int cnt, int start) {
        if (cnt == N) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                sum = operators[i] == 0 ? sum - numbers[i] : sum + numbers[i];
            }

            if(sum == target){
                answer ++;
            }
            return;
        }

        for (int i = start; i < 2; i++) {
            operators[cnt] = i;
            perm(cnt + 1, start);
        }
    }
}

 

두번째 풀이 - DFS

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


    private static void dfs(int[] numbers, int target, int index, int sum) {

        if (index == numbers.length) {
            if(target == sum){
                answer++;
            }
            return;
        }
        dfs(numbers, target, index + 1, sum + numbers[index]);
        dfs(numbers, target, index + 1, sum - numbers[index]);
    }
}