굥뷰를 햡시댜
[Programmers] 타겟 넘버 본문
https://programmers.co.kr/learn/courses/30/lessons/43165
dfs로 풀었습니다.
이 문제는 이진트리의 구조를 이해하는 것이 중요합니다.
모든 경우를 더했을 경우 + 뺐을 경우의 수를 재귀로 구현했습니다.
#include <string>
#include <vector>
using namespace std;
int answer = 0;
void dfs(vector<int> &numbers, int target, int sum, int index) {
if(index >= numbers.size()) {
if(sum == target) answer += 1;
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;
}
'알고리즘 문제 풀이 > KaKao 문제 풀이' 카테고리의 다른 글
[Programmers] 위장 (0) | 2019.10.11 |
---|---|
[Programmers] 전화번호 목록 (0) | 2019.10.11 |
[Programmers] 네트워크 (0) | 2019.10.11 |
[Programmers] 단어 변환 (0) | 2019.10.11 |
[Programmers] 영어 끝말잇기 (0) | 2019.10.08 |
Comments