문제설명
.
처음에 문제를 대충읽고 인풋에 - , + 지정해서 주는 수열 인줄알고 투포인터로 접근하려다, result 값을 보니 이해가 안돼서 다시 읽어봤더니, 넘겨 받는 수열에서 각각 수들의 부호를 일일이 넣어서 확인해보는 단순한 백트래킹 문제였다.
문제풀이를 딱히 설명한다면... 백트래킹...밖에 할 말이 없는 문제였다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <string> #include <vector> using namespace std; int targets; int answers; int sum = 0; void dfs(int num, vector<int>numbers) // 백트래킹 { if (num == numbers.size()) { if (sum == targets) { answers++; } return ; } sum += numbers[num]; dfs(num+1,numbers); sum -= numbers[num] * 2; dfs(num+1,numbers); sum += numbers[num]; } int solution(vector<int> numbers, int target) { targets = target; dfs(0,numbers); return answers; } | cs |
