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

문제

https://programmers.co.kr/learn/courses/30/lessons/43165

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

 

 

풀이

쉬운 DFS 문제

재귀를 이용해서 해결했음!

항상 다음 단계를 가기 전에 뭔가를 계산했으면 그 단계를 해결하고 나면 다시 돌려 놓기!!

 

자세한건 주석으로!

 

 

코드

// 코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버
// https://programmers.co.kr/learn/courses/30/lessons/43165

package PROGRAMMERS.level2;

public class Num43165_타겟넘버 {
    private static class Solution {
        static int answerCount; // 계산한 값이 타겟 넘버와 같으면 1증가
        private int solution(int[] numbers, int target) {
            int sum = 0; // 배열의 있는 수를 더하거나 빼면서 진행. 그 계산 결과를 담을 바구니
            answerCount = 0;
            solution(numbers, 0, target, sum);

            int answer = answerCount;
            return answer;
        }

        // dfs
        // 주어진 배열, 현재 위치 인덱스, 타겟 넘버, 계산 중인 값
        private void solution(int[] numbers, int index, int target, int sum) {
            // 배열에 있는 값들을 다 사용한 경우
            if (numbers.length == index) {
                // 계산 결과가 타겟 넘버와 같으면
                if (sum == target) {
                    answerCount++;
                }
                return;
            }
            
            sum += numbers[index]; // + 계산
            solution(numbers, index + 1, target, sum);
            sum -= numbers[index]; // 돌려 놓기

            sum -= numbers[index]; // - 계산
            solution(numbers, index + 1, target, sum);
            sum += numbers[index]; // 돌려 놓기
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(sol.solution(new int[]{1, 1, 1, 1, 1}, 3));
        System.out.println(sol.solution(new int[]{4, 1, 2, 1}, 4));
    }
}