(알고리즘 스터디) 5주차 월 _ DFS&BFS 🤿 _ (Programmers) 타겟 넘버

🌟 프로그래머스 / DFS&BFS / Level 2 / 타겟넘버

📃 문제

프로그래머스

🚫 제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

👀 입출력 예

 

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

🤔 풀이 방법

1️⃣ 생각 정리

① 한번씩만 사용가능
② 더하기 또는 빼기 가능
③ 중요한건 마지막에 타깃 넘버가 되었는지
④ 숫자의 순서보다 중요한건 단순히 + / - 부호 일것

2️⃣ 해결 방법

➡️ ② (더하기 & 빼기) 의 내용을 잘 구현하는 것이 중요하다.

① 이진 트리 구조로 +4 -4 이런식의 숫자를 더해간다
➡️ dfs 돌릴 때 두가지 버전으로 돌린다.?
dfs (depth+1, arr, sum+num);
dfs (depth+1, arr, sum-num);
이렇게 하니깐 StackOverFlow Error 발생

② 그럼 애초에 배열을 +4, -4, +2, -2 이렇게 만들어서 돌릴까?
➡️ 훑는 과정이 어려움

③ ① 의 방법을 수정 후 재시도

3️⃣ 작동 과정

➡️ 마침 유튜브 동영상 내용 중 내가 생각한 내용을 잘 정리해놓은 그림이 있어서 가지고 와봤다.

출처 : https://www.youtube.com/watch?v=S2JDw9oNNDk

💻 풀이 코드

class Solution {
    public static int[] numbers;
    public static int target;
    public static int answer;
    
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        this.answer = 0;
        
        dfs (0,0);
        
        return answer;
    }
    public static void dfs (int depth, int sum) {
        if (depth == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }
        
        dfs(depth + 1, sum + numbers[depth]);
        dfs(depth + 1, sum - numbers[depth]);
    }
}

 

 

[level 2] Title: 타겟 넘버, Time: 0.39 ms, Memory: 71.8 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@904cf50

🔗 참고

① 타겟넘버 DFS 재귀함수 (https://www.youtube.com/watch?v=S2JDw9oNNDk)