항해99 24일차 TIL( 타겟 넘버 / 프로그래머스)

문제         

프로그래머스

1 번째 시도   

• DFS 이용
• 마지막 노드까지 도착했을 때 타켓 숫자면 카운팅
• DFS 파라미터에 들어가야 할 것들
  • DFS 실행시킬 배열
  • 깊이
  • 타켓 넘버
  • 이전합

//dfs로 플러스 마이너스 다 붙여가며 해당 숫자 카운트

import java.util.*;

class Solution {
    int answer = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target, 0);
        return answer;
    }
    
   
    void dfs(int[] numbers, int depth, int target, int exSum) {

        if(depth == numbers.length) {
            if(target == exSum) {
                answer++;
            }
        }
        else {
            dfs(numbers,depth+1, target, exSum+numbers[depth]);
            dfs(numbers,depth+1, target, exSum-numbers[depth]);
        }
    }
}

 

 

배움

• dfs는 꼭 for 문을 사용해야 한다는 잘못된 생각을 깨줌