[DFS/BFS] 타겟 넘버

yerin6860·2020년 8월 28일
0

프로그래머스

목록 보기
15/30
post-thumbnail

|| 문제설명 ||

  1. n개의 음이 아닌 정수가 있다.
  2. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다.
  3. 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성하라.
  • numbers : 사용할 수 있는 숫자가 담긴 배열
  • target : 타겟 넘버

    _ 주어지는 숫자의 개수 : 2개 이상 20개 이하
    _ 각 숫자 : 1 이상 50 이하, 자연수
    _ 타겟 넘버 : 1 이상 1000 이하, 자연수


|| 문제해결방법 ||

- DFS로 모든 경우의 수를 찾아봄
- answer → 전역변수로 전환   
- 모든 경우에 있어 재귀함수를 통해 sum에 각 결과를 더함
- if (sum == target) 일 경우 answer++;
- numbers.size() == 0  이면 return;

|| 코드 ||

[2020.08.25] 성공
#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int target, int sum) {
    if(numbers.empty()) {
        if(sum == target) answer++;
        return;
    }
    int p = sum + numbers.back();
    int m = sum - numbers.back();
    numbers.pop_back();
    dfs(numbers, target, p);
    dfs(numbers, target, m);
}
int solution(vector<int> numbers, int target) {
    dfs(numbers, target, 0);
    return answer;
}

0개의 댓글