프로그래머스 타겟 넘버

경우의 수는 +, -로 N제한이 20이므로 2^20의 시간복잡도는 1초 안에 충분히 해결할 수 있는 문제다. DFS를 통한 완전탐색으로 해결했다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_타겟넘버.cpp

 

	#include <string>
	#include <vector>
	using namespace std;
	void go(int idx, int sum, const vector<int> &numbers, int &cnt, int target) {
	if(idx == numbers.size()) {
	if(sum == target) {
	cnt += 1;
	}
	return;
	}
	go(idx + 1, sum + numbers[idx], numbers, cnt, target);
	go(idx + 1, sum - numbers[idx], numbers, cnt, target);
	}
	int solution(vector<int> numbers, int target) {
	int answer = 0;
	go(0, 0, numbers, answer, target);
	return answer;
	}

view raw Progammers_타겟넘버.cpp hosted with ❤ by GitHub