알고리즘/Programmers
[프로그래머스/C++] 타겟 넘버
chaeD2
2022. 6. 11. 17:17
https://programmers.co.kr/learn/courses/30/lessons/43165
코딩테스트 연습 - 타겟 넘버
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수
programmers.co.kr
구현
재귀 DFS를 이용해서 쉽게 풀 수 있다.
{1, 1, 1, 1, 1}이라면 [0]을 +로 하는 가지, -로 하는 가지로 나누어서 그 안에서 또 +[1]로 하는 가지와 -[1]로 하는 가지로 나누어서 벡터를 끝까지 순회하면 된다. 끝까지 순회하면 더한 값과 target을 비교하여 판단하면 된다.
// [프로그래머스 코테 고득점 Kit] BFS/DFS - 타겟 넘버
#include <string>
#include <vector>
using namespace std;
int result = 0;
void dfs(vector<int>& v, int sum, int target, int cnt) {
if (cnt == v.size()) {
if (sum == target) {
result++;
}
return;
}
dfs(v, sum - v[cnt], target, cnt + 1);
dfs(v, sum + v[cnt], target, cnt + 1);
}
int solution(vector<int> numbers, int target) {
int answer = 0;
int cnt = 0;
// 매개 변수로 들어가는 cnt를 cnt++로 넣어 줬는데, 이렇게 하면 안 된다.
// 이 줄에서의 cnt는 solution 지역에서의 cnt이기 때문에,
// cnt++는 solution 지역에서의 cnt가 증가될 뿐, 매개변수로 들어가는 cnt에는 아무런 영향을 주지 않는다.
dfs(numbers, -numbers[0], target, cnt + 1);
dfs(numbers, +numbers[0], target, cnt + 1);
answer = result;
return answer;
}
int main() {
vector<int> v = { 1,1,1,1,1 };
solution(v, 3);
}