[PS] 99클럽 코테 스터디 34일차 TIL (타겟 넘버)

문제

문제 링크

설명

numbers 배열의 각 항목을 더하거나 빼는 과정 중 target 의 숫자와 같아지는 경우의 수를 찾는 문제.

풀이

문제 접근 방향

• 더하거나 빼는 두 가지 선택지가 있다.
• 첫 번째 숫자부터 시작해 더하거나 빼고, 그 결과를 다음 숫자에 전달하는 식으로 재귀적으로 접근한다.
• dfs 함수에서 더하거나 빼는 경우에 대해 재귀 호출한다.
• 기저 조건 :
  • dfs 를 numbers 배열 길이 만큼 호출했으면 종료시킨다. (모든 항목을 탐색했다는 의미)
  • sum 이 target 과 같은 경우 카운트를 증가시킨다.

dfs 과정을 몇가지 경우만 대략적으로 그려보면 아래와 같다. dfs 가 한번 호출될 때마다 sum 에 대해 더하는 경우와 빼는 경우를 모두 탐색한다. 그 과정에서 sum 과 target 이 같은 경우엔 answer 의 갯수를 하나씩 증가시켜 준다.

class Solution {
  static int answer = 0;

  public int solution(int[] numbers, int target) {
    answer = 0; // 호출 시 answer 초기화
    dfs(numbers, target, 0, 0);
    return answer;
  }

  private void dfs(int[] numbers, int target, int index, int sum) {
    if (index == numbers.length) { // index 증가 제한 조건
      if (sum == target) {  // 카운트 조건
        answer++;
      }
      return;
    }
    dfs(numbers, target, index + 1, sum + numbers[index]);
    dfs(numbers, target, index + 1, sum - numbers[index]);
  }
}