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

🔗 타겟 넘버

두 번째 테스트케이스

 

주어진 숫자 배열에서 각 숫자를 더하거나 빼서 특정 타겟 숫자를 만들 수 있는 모든 경우의 수를 찾는 문제로, 가능한 모든 조합을 탐색하기 때문에 완전탐색이다.

 

🥊 접근 방법 🥊

numbers 값을 계속 더하다가 target 값이 안 나오면 빠꾸해서 값을 빼주면 되겠다고 생각했다. 비슷한 문제를 풀어본 적이 있어서 바로 DFS를 떠올렸다.

 

DFS

DFS를 사용해 각 숫자에 더하기(+), 빼기(-) 두 가지 경우 모두를 탐색한다.

// basis part
if(i == numbers.length){
    if(total == target) answer++;
    return;
}
        
// inductive part
DFS(numbers, target, i+1, total + numbers[i]);  // 그림의 초록색 부분
DFS(numbers, target, i+1, total - numbers[i]);  // 그림의 주황색 부분

 

 

✨ 전체코드 ✨

• total : numbers의 원소들을 더한 값
• answer : 경우의 수

class Solution {

    static int answer;
    
    public int solution(int[] numbers, int target) {
        answer = 0; 
        DFS(numbers, target, 0, 0);
        return answer;
    }
    
    
    public static void DFS(int[] numbers, int target, int i, int total){
        // basis part
        if(i == numbers.length){
            if(total == target) answer++;
            return;
        }
        
        // inductive part
        DFS(numbers, target, i+1, total + numbers[i]);
        DFS(numbers, target, i+1, total - numbers[i]);
    }
}

 

🌀 성능

• 메모리 : 72.6 MB
• 시간 : 0.35 ms

 

🥕 비슷한 문제

• 백준 연산자 끼워넣기
• SWEA 햄버거 다이어트