[프로그래머스] 43165 : 타겟 넘버

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

프로그래머스

 

재귀 함수 작성시 고려할 점

재귀는 3가지를 고려하면 된다.

다음 경우, 불가능한 경우(종료 조건1), 리턴값 경우(종료 조건2) 

 

이 문제가 완전탐색이고 그 중 DFS인 이유

이 문제는 주어진 숫자를 더하거나 빼서 target(특정 값)에 도달하는 경우의 수를 구하는 문제이다.

모든 경우를 고려해야하므로 완전탐색이고, 완전 탐색을 하기 위해서는 여러 알고리즘 방법(DFS, BFS, 백트래킹, 브루트포스, DP..)이 있다.

DFS

1. 더하거나 빼므로 트리 구조를 생각할 수 있다.

2. 모든 숫자에 대해 탐색을 완료하고(더하거나 빼면서) 끝에 도달할 경우(=리프노드 도달) target과 합이 같은지 확인한다.

 

위를 고려하여 재귀 함수 코드를 작성하면 문제를 해결할 수 있다.

 

코드

#include <bits/stdc++.h>

using namespace std;

int makeTarget(vector<int> &numbers, int target, int totalSum, int pos){
    if (pos==numbers.size()) {
        return target==totalSum? 1 : 0;
    }
    return makeTarget(numbers, target, totalSum+numbers[pos], pos+1)+ makeTarget(numbers, target, totalSum-numbers[pos], pos+1);
}

int solution(vector<int> numbers, int target) {
    
    return makeTarget(numbers, target, 0, 0);
}