99클럽 코테 스터디 11일차 TIL + DFS(타겟 넘버)

오늘의 과제

프로그래머스 Lv.2에 정렬로 분류된 타겟 넘버입니다.

 

어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.

문제

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

프로그래머스

 

 

먼저 문제 요구사항 요약입니다.

 

n개의 음이 아닌 정수들이 주어질 때, 이 수들을 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는

경우의 수를 return 해주면 됩니다.

 

문제의 주제처럼 어제 활용한 DFS를 활용하면 되는데 간단하게 설명하면

주어진 배열을 탐색하며 더했을 때의 경우와, 뺏을 때의 경우의 분기로 뻗어나가

총 합이 타겟과 동일할 때 경우의 수를 추가해주면 됩니다.

 

즉, 아래 그림처럼 numbers의 매 자리수마다 두 가지의 가지가 뻗어나간다고 생각하시면 이해가 편합니다.

여기서 L1, L2, L3는 numbers의 각 요소라 생각하면 편합니다.

 

구현이 간단한만큼 코드 또한 간단합니다.

class Solution {
    
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {
        DFS(0, numbers, 0, target);
        return answer;
    }
    
    public void DFS(int sum, int[] numbers, int idx, int target) {
        if (idx >= numbers.length) {
            if (sum == target) answer++;
            return;
        }
        // 더했을 때
        DFS(sum + numbers[idx], numbers, idx + 1, target);
        // 뺏을 때
        DFS(sum - numbers[idx], numbers, idx + 1, target);
    }
}

 

 

배운 점

어제의 기억 덕분인지, 문제가 간단해서 그런지 매우 쉽게 풀어낸 문제입니다.

 

일부러 연계해서 문제를 선정하는 것 같은데 흔들리지 않고 꾸준히만 해낸다면

다음 회차에는 Lv.3도 간간히 도전할 수 있을 것 같습니다.

 

스스로 무언가 공부하는 습관이 들여지지 않은 사람의 경우 지금 하고 있는 항해 99처럼

동기부여를 할 수 있는 프로그램을 찾아 움직이면 최초 습관 들이는데에는 많은 도움이 될 것 같습니다.

 

 

 

오늘의 한줄평

스스로 움직일 동기가 부족하다고? 돈을 써라. 최고의 동기가 될거다.