[BFS,DFS] 타겟넘버

[프로그래머스] 깊이/너비 우선탐색(BFS/DFS) 타겟넘버

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

*재귀를 활용

package com.company;

public class TargetNumber {

    static int TARGET = 3;
    static int ANSWER_COUNT = 0;

    public static void main(String[] args) {
        int[] numbers = {1,1,1,1,1};
        makeOperator(numbers, 0);
    }

    private static void makeOperator(int[] numbers, int k) { //k는 number의 index

        if(k < numbers.length){
            numbers[k] *=1;
            makeOperator(numbers,k+1);

            numbers[k] *=-1;
            makeOperator(numbers,k+1);
        }

        else{
            int sum=0;
            for(int num: numbers){ sum += num; }
            if(sum==TARGET) ANSWER_COUNT++;
        }
    }
}

두번째 풀기(2019. 04. 12)

이 글이 이 블로그 조회수 1위이다. 다시 풀어봤다.

public class Main {

    static int answer=0;
    static int TARGET=4;

    public static void main(String[] args){
        int[] numbers = {1, 3};
        rec(numbers, 0, 0);
        System.out.println(answer);

    }

    static void rec(int[] numbers, int sum, int index){

        //종결
        if(index == numbers.length){
            if(sum==TARGET) answer++;
            return
        }

        rec(numbers, sum+numbers[index], index+1);
        rec(numbers, sum-numbers[index], index+1);
    }
}