[Java] 프로그래머스 Lv2.타겟넘버

➡️문제 링크

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

 

 

💡아이디어

DFS

 

 

✏️문제 풀이

1. DFS - 성공

문제를 읽다보면 결국 numbers 배열 안의 원소들이

어떨 때는 +로, 또 어땔 때는 -로 더해지는 것을 확인할 수 있다

그래서 이 두 가지 경우로 나누어 dfs를 돌리며

이 때, 현재 몇 번째 원소를 더해야하는지와 이전까지의 합을 매개변수로 설정한다.

그 뒤로는 배열의 마지막까지 도달하면 합이 target과 같은지 확인하고 return!

import java.util.*;

/*
dfs 접근해보기
*/
class Solution {
    static int answer = 0;
    static int[] numbers;
    static int target;
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        
        dfs(0, 0);
            
        return answer;
    }
    
    static void dfs(int count, int sum){
        if(count == numbers.length){
            if(sum == target) answer++;
            return;
        }
        
        dfs(count+1, sum+numbers[count]);   // 덧셈
        dfs(count+1, sum-numbers[count]);   // 뺄셈
    }
}

 

 

 

 

 

+)

여담으로 이 문제 매번 볼 때마다

dp인가? 완탐인가? Lv2라는데 왜 나는 못 풀지? 왜 dfs로 접근하라는거야?

라며 매번 나에게 좌절감을 안겨 준 문제였다

그런데 이번에 프로그래머스 새 계정을 파면서

첫 문제로 이 문제를 푸는데

전과 달리 파바박 풀었다!

물론 알고리즘 고득점 kit에서 골라서

유형이 깊이/너비 우선 탐색(DFS/BFS)라는 걸 알았지만

확실히 전과는 달라졌다는 걸 느꼈다

 

앞으로 문제를 풀며

좌절하는 때가 분명있을 것이라고 생각하지만

그럼에도 불구하고포기하지 않고 성실하게 풀어야징-