#include <string>
#include <vector>
using namespace std;
void dfs(vector<int>& vecNumber, int sum, int n, int& answer, int& iSize, int iTarget)
{
if (n == iSize)
{
if (iTarget == sum)
{
answer++;
return;
}
else
return;
}
// 모든 vec의 하나하나숫자를 -와 + 두개 모두 넣어주기
dfs(vecNumber, sum + vecNumber[n], n + 1, answer, iSize, iTarget);
dfs(vecNumber, sum - vecNumber[n], n + 1, answer, iSize, iTarget);
}
int solution(vector<int> numbers, int target)
{
int answer = 0;
int iSize = numbers.size();
dfs(numbers, 0, 0, answer, iSize, target);
return answer;
}
솔직히 좀 헤맸다.
어렵지 않은 문제라 for 가지고 하려 했는데 생각보다 어려웠다.
아무리 해도 안돼서 문제 다시 봤더니 DFS, BFS... 재귀 함수로 하나하나 다 넣어주면 되는 문제... ㅎㅎ...
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> numbers, int target)
{
int answer = 0;
int size = 1 << numbers.size();
for (int i = 1; i < size; i++)
{
int temp = 0;
for (int j = 0; j < numbers.size(); j++)
{
if (i & (1 << j))
temp -= numbers[j];
else
temp += numbers[j];
}
if (temp == target) answer++;
}
return answer;
}
이건 프로그래머스의 비트의 마법사... 보고 배우면 좋을 거 같아서 가져왔습니다.
'오늘의 알고리즘' 카테고리의 다른 글
[C++]완전탐색 모의고사(프로그래머스 1레벨) (0) | 2022.02.03 |
---|---|
[C++]정렬 K번째수(프로그래머스 1레벨) (0) | 2022.02.02 |
[C++]동적계획법(Dynamic Programming) N으로 표현(프로그래머스 3레벨) (0) | 2022.01.31 |
[C++]힙(Heap) 더 맵게(프로그래머스 2레벨) (0) | 2022.01.30 |
[C++]스택/큐 기능개발(프로그래머스 2레벨) (0) | 2022.01.30 |