[프로그래머스 Level2] 타겟 넘버(JAVA)

문제

---

출처 - https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 

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

 

 

 

 

 

문제 풀이

---

• 주어진 n 제한이 20이하로 작은 수 이다. -> 완전탐색을 생각할 수 있다.
• '-' 인경우, '+' 인 경우 두 가지를 '선택' 하여 타겟 넘버를 만들 수 있다.
• 따라서 조합을 사용하여 모든 경우를 체크할 수 있다. 시간복잡도 O(2^20)
• 인덱스는 배열의 길이 +1  지점에서 종료된다. 그때까지 더하거나 뺀 수의 결과가 target과 같은지 판단 
• 첫 인덱스의 앞에 - 가 붙을 수 있는 점을 주의한다.

 

 

소스 코드

---

//프로그래머스 타겟 넘버
class Solution {
    static int count = 0;
    public int solution(int[] numbers, int target) {
        int answer = 0;

        dfs(0,numbers,target,0);
        
        answer = count;
        return answer;
    }
    
    public void dfs(int index, int[] numbers, int target, int sum){
        if(index == numbers.length) { 
            if (sum == target) {
                count++;
            }
            return;
        }
        
        dfs(index+1, numbers,target,sum+numbers[index]); //더하는 경우
        dfs(index+1, numbers,target,sum-numbers[index]); //빼는 경우
        
    }
}