[프로그래머스] Lv.2 타겟 넘버 JAVA 풀이

문제 Lv.2 타겟 넘버 (dfs, bfs)

n개의 음이 아닌 정수

정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만들자

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있다

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs 

 

 

 1. count 계산은 맨 마지막에

• 모든 넘버들을 다사용해서 타겟넘버를 만들어야해서 마지막까지 가고나서 타겟넘버랑 같으면 count++
• 각자 타고 타고 들어가 dfs를 실행하면 count 별도 연산 없이도 차곡차곡 쌓인다!
  -> 최종적으로 solution메서드에서 그렇게 쌓인 count만 출력해주면 끝

 

 2. for문을 구현할까 했지만 그냥 인자로 계산하기!

• 넘버들을 for문으로 돌릴까 했지만 구간구간마다 + 혹은 - 해줘야하기때문에 sum과 number[depth]를 사용!
• 모든 넘버들을 다 탐색해야하고 depth를 사용해서 구간마다 봐주기 때문에 visit이 필요없다
• 조건없이 + 따로, - 따로 dfs를 각각 실행하주고 모든 레이어를 다 돌았을 때 타겟넘버가 됐냐 안됐냐만 파악해주고 종료하면 된다       

 

 

 [코드]

class Solution {
    static int count =0;
    public int solution(int[] numbers, int target) {

        dfs(numbers, 0, 0, target);
        
        return count;
    }
    static void dfs(int[] numbers, int depth, int sum, int target)
    {
        if(depth == numbers.length){
            if(sum==target){
                count++;
            }
            return;
        }
        dfs(numbers, depth+1, sum+numbers[depth], target);
        dfs(numbers, depth+1, sum-numbers[depth], target);
    }
}

 

 [해설]

 

    static int count =0;
    public int solution(int[] numbers, int target) {

        dfs(numbers, 0, 0, target);  numbers, target은 그냥 dfs에서도 참고하고 싶어서 넣은 것 (연산하지는 않음)
        return count;  답
    
    static void dfs(int[] numbers, int depth, int sum, int target)
    {
        if(depth == numbers.length){  모든 넘버 다 돌리면 연산 끝
            if(sum==target){  합산 값이 목표하는 타겟 넘버가 되었으면 카운트
                count++;  
            }
            return;  depth 끝났으니 종료
        }
        dfs(numbers, depth+1, sum+numbers[depth], target);  구간 + 해서 sum 값 넣기
        dfs(numbers, depth+1, sum-numbers[depth], target);  구간 - 해서 sum 값 넣기
    }
}

 

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

프로그래머스