Life Engineering
[프로그래머스] 타겟 넘버 (C++) 본문
https://programmers.co.kr/learn/courses/30/lessons/43165
#include <string>
#include <vector>
using namespace std;
int cnt=0;
void dfs(vector<int>& numbers, int target, int depth, int limit, int result){
if (depth==limit){
if (result==target){
cnt++;
}
return;
}
dfs(numbers, target, depth+1, limit, result+numbers[depth]);
dfs(numbers, target, depth+1, limit, result-numbers[depth]);
}
int solution(vector<int> numbers, int target) {
dfs(numbers, target, 0, numbers.size(), 0);
return cnt;
}
DFS 를 이용하여 탐색하는 문제.
1 depth마다 2가지 경우의 수가 존재한다.(더하느냐, 빼느냐).
DFS 방식으로 탐색한다. 이때 depth가 limit이면(즉 numbers의 크기이면), 그간의 결과값이 target 과 일치하는지 체크한다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 가장 먼 노드 (C++) (0) | 2021.09.27 |
---|---|
[프로그래머스] 디스크 컨트롤 (C++) (0) | 2021.09.24 |
[프로그래머스] 소수 찾기 (C++) (0) | 2021.09.22 |
[BOJ 16236] 아기 상어 (C++) (0) | 2021.09.17 |
[프로그래머스] 단체사진 찍기 (C++) (0) | 2021.09.16 |