21.07.07 - [PG] 타겟 넘버

[suhyunsim]

문제

• 타겟 넘버

핵심 아이디어

• DFS(재귀함수)를 활용

1. 경우의 수 계산: 최악의 경우에 수행할 연산 횟수를 계산해서 재귀함수/완전탐색을 사용해도 될 지 확인

• 2 ^ 20 -> 100만번 < 500만번 => 재귀로 풀어도 되겠다!

2. 수행동작: 재귀함수가 호출됐을 때 한 턴마다 수행할 동작 구현
3. 탈출조건: 어느 시점에 이 재귀함수를 끊을지 구현

• 현재 재귀함수가 call된 인덱스가 numbers.length만큼 되면 빠져나올 조건(해당 인덱스에는 더하거나 뺄 숫자가 없으니까)

어려운 점, 실수

풀이

package main.java.com.poogle.PG.Q43165;

public class Solution {

    static int answer, target;
    static int[] numbers;

    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 1, 1, 1, 1}, 3));
    }

    public static int solution(int[] numbers, int target) {
        answer = 0;
        Solution.target = target;
        Solution.numbers = numbers;
        
        dfs(0, 0);
        
        return answer;
    }
    
    private static void dfs(int sum, int i) {
        //1. 탈출 조건
        if (numbers.length == i) {
            if (target == sum) answer++;
            return;
        }
        
        //2. 실행 동작
        dfs(sum + numbers[i], i + 1);
        dfs(sum - numbers[i], i + 1);
    }
}