[프로그래머스] 타겟넘버

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int target, int sum, int count){
    if(count == numbers.size()){
        if(sum == target) answer++;
        return;
    }
    dfs(numbers, target, sum + numbers[count], count + 1);
    dfs(numbers, target, sum - numbers[count], count + 1);
}

int solution(vector<int> numbers, int target) {
    dfs(numbers, target, 0, 0);
    return answer;
}

저번주에 풀다가 한번 손을 놓았던 문제이다.

 

같이 스터디를 하는 분에게 설명을 들어가며 이해와 풀이에 성공했다.

 

'닥터 스트레인지' 라는 예시를 들어준것이 이해의 키였다.

 

재귀함수를 이용한 반복으로 문제를 해결하였으며, 회전수는 numbers의 크기만큼 돌리며, 끝가지 가는 동안의 모든 분기를 하나하나 살펴 답까지 도달하는것이다.

 

예를들어 numbers가 {1, 1, 1, 1, 1} 일 경우에는 첫 분기에서 +1인 경우와 -1 인 경우로 나뉘고, +1인 경우의 분기 안에서 다시한번 +1인 경우와 -1 인 경우로 나뉘게된다.

 

이해하기 쉽게 그려본 것

 

numbers의 크기만큼 반복하면 안에 들어있는 숫자들이 +인경우, -인경우를 다 따져서 결과를 내고, 마지막 반복시 원하는 결과값, 즉 target과 값이 동일한가를 확인하고 answer에 값을 추가해준다.

 

즉, 1 5개를 더하고 빼는 모든 분기에서 결과가 3이 나오는 횟수를 answer로써 출력해주는 것.

 

곱했을때와 나누었을때 까지 사용을 하면 함수내 제일 아래에 *를 사용하는것, /를 사용하는것 총 두줄만 추가해주면 제대로 작동하였다.

 

다만, 순서는 고정이 되어있으므로 간단하게 끝나는것 같지만, 만약 numbers의 순서를 바꿔서 모든 결과를 도출하는 것이라면 어떨까?

 

코드 자체는 엄청 무거워지겠지만, numbers의 모든 숫자 배치의 가능성을 두고 바깥쪽에서 바꿔가며 돌리면 될것같다.

 

 

문제출처 : programmers.co.kr/learn/courses/30/parts/12421

프로그래머스

* 제 생각이 틀렸거나 보강해주실수 있는 부분이 있다면 댓글로 지식을 나누어주시면 큰 도움이 됩니다!