프로그래머스 타겟 넘버 (DFS)
[1, 1, 1, 1, 1] 로 더하기 또는 빼기를 반복하여 타겟 넘버인 3을 만들 수 있는 방법의 수는 위와 같이 5가지이다.
주어진 수가 [a, b, c, d, e]가 있다고 하면, 이 수들로 더하기 또는 빼기를 반복하여 만들 수 있는 경우의 수는 각각 수별로 + 또는 -를 하는 방법 2가지이므로 2의 5제곱 32가지이다.
a부터 e 까지, + 또는 - 연산을 해가며 타겟 넘버가 되는지 판단하면 된다.
여기서, 지금까지 연산한 결과에 + 또는 - 연산한 결과를 또 연산해가며 탐색하므로 재귀 방식을 생각해 볼 수 있다.
이런식으로 +1로 시작할 떄의 트리(그래프)를 생각해본다.
또한 전역변수 answer(타겟넘버를 만드는 경우의 수를 저장하는 변수) 를 선언하였다고 가정하자.
그래프의 탐색 방법 중 DFS로 탐색을 진행해 나가며 numbers 배열에 있는 숫자를 다 사용했을 때, 그 때의 노드가 타겟 넘버와 같으면 answer 에 1을 더해 나가며 답을 구한다.
일단 무한 루프에 빠지지 않도록, 재귀 함수의 종료 조건을 먼저 정의한다.
•
탐색 시, numbers 벡터의 모든 원소를 사용하였으면 return 해야 한다.
◦
(numbers.size() 와 numbers 벡터의 인덱스를 가리키고 있는 index 변수의 값이 같으면 numbers 벡터의 모든 원소를 사용하였다는 뜻)
◦
또한 모든 원소를 사용하였으며, 그 때의 합이 타겟 넘버와 같으면 전역변수 answer 에 1을 더해준다.
재귀함수 안에서 numbers 벡터의 다음 원소를 더하는 경우와, 빼는 경우를 나누어 재귀적으로 호출한다.
더하고 빼가며 합을 저장할 sum 변수와 numbers 벡터의 인덱스를 참조할 index 변수가 필요하고, 이들은 재귀함수의 매개변수로 선언되어 각각 호출된 함수에서 사용되어야 한다.
#include <iostream>
#include <vector>
using namespace std;
int answer = 0;
void dfs() {
if (index == numbers.size()) {
if (sum == target) answer++;
return;
}
dfs(numbers, target, sum+numbers[index], index+1);
dfs(numbers, target, sum-numbers[index], index+1);
}
int solution(vector<int> numbers, int target) {
dfs(numbers, target, 0, 0);
return answer;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, data, target;
vector<int> numbers;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> data;
numbers.push_back(data);
}
cin >> target;
cout << solution(numbers, target);
}
C++
복사