[43165] 타겟 넘버

✔ 타겟 넘버

[프로그래머스 43165]

문제 분석하기

이전 노드의 합에 현재 노드의 값을 빼거나 더하는 경우로 깊이 우선 탐색을 진행한 후

마지막 합의 값과 타겟 값이 일치할 경우 타겟 넘버를 만드는 방법의 수를 증가

손으로 풀어보기

1. 깊이 우선 탐색을 진행
   • 현재 노드의 값을 빼거나 더하는 경우로 진행
2. 마지막 노드까지 진행했을 때 합의 값과 타겟 값이 일치할 경우 타겟 넘버를 만드는 방법의 수를 증가
   • numbers의 길이와 탐색 깊이가 같다면 마지막까지 수행한 것
3. 타겟 넘버를 만드는 방법의 수 반환

슈도코드 작성하기

numbers(사용할 수 있는 숫자가 담긴 배열)
target(타겟 넘버)
answer(타겟 넘버를 만드는 방법의 수)
dfs(numbers, 0, target, 0) 수행

dfs(numbers, depth, target, sum) {
    if(마지막 노드까지 수행했다면) {
        if(타겟 넘버과 합의 값이 같다면) {
            answer 증가
        }
    }
    dfs(numbers, depth + 1, target, sum + numbers[depth])
    dfs(numbers, depth + 1, target, sum - numbers[depth])
}

코드 구현하기

/**
 * 43165) 타겟_넘버
 */
public class K001_43165 {
    // answer(타겟 넘버를 만드는 방법의 수)
    static int answer = 0;

    // numbers(사용할 수 있는 숫자가 담긴 배열)
    // target(타겟 넘버)
    public int solution(int[] numbers, int target) {
        // dfs(numbers, 0, target, 0) 수행
        dfs(numbers, 0, target, 0);
        return answer;
    }

    // 깊이 우선 탐색
    private void dfs(int[] numbers, int depth, int target, int sum) {
        // 마지막 노드까지 수행했다면
        if (depth == numbers.length) {
            // 타겟 넘버과 합의 값이 같다면
            if (target == sum) {
                // answer 증가
                answer++;
            }
            return;
        }
        // 현재 노드의 값 더하기
        dfs(numbers, depth + 1, target, sum + numbers[depth]);
        // 현재 노드의 값 빼기
        dfs(numbers, depth + 1, target, sum - numbers[depth]);
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K001_43165 solution = new K001_43165();

        int[] numbers = { 1, 1, 1, 1, 1 };
        int target = 3;

        int result = solution.solution(numbers, target);

        System.out.println(result);
    }
}