[프로그래머스] 2단계 - 타켓 넘버

문제 설명

사용할 수 있는 숫자가 담긴 배열이 있을 때, 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 return

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

문제 풀이법

이 문제는 dfs를 통해서 풀 수 있다 

 

dfs 함수의 매개변수는 현재 numbers의 인덱스, 현재 계산된 값, 그리고 숫자들이 담긴 벡터이다

dfs 함수의 종료 조건은 인덱스가 numbers의 사이즈와 같다면 종료하는데, 이때 총 계산된 값이 타겟 넘버와 같은지 확인하고 종료한다

 

인덱스가 numbers의 사이즈와 같지 않다면 아직 더 계산해야하는 숫자가 남았다는 뜻이므로 for문을 돌면서 dfs를 2번씩 더 수행한다

지금까지 계산된 값에 + numbers[idx] 를 하는 경우랑 - numbers[idx]를 하는 경우를 위해 for문을 통해서 dfs 함수를 돌려주었다

사실 지금 생각해보면 굳이 for문 안쓰고 그냥 dfs() 두번 써도 됐었을 것 같다 (그게 더 효율적이었을 것 같은데 항상 좋은 방법은 블로그 쓸 때 생각이 나서.....)

 

이렇게 하면 각각의 numbers에 +, - 하는 경우 전부를 돌 수 있다

 

소스 코드

#include <string>
#include <vector>

using namespace std;

char oper[2] = { '+', '-' };

int numbers_size = 0;
int target_num = 0;
int answer = 0;

void dfs(int idx, int sum, vector<int> numbers) {
    if (idx == numbers_size) {
        if (sum == target_num)
            answer++;
        return ;
    }
    
    for (int i = 0; i < 2; i++) {
        int tmp = sum;
        if (oper[i] == '+')
            tmp += numbers[idx];
        else
            tmp -= numbers[idx];
        
        dfs(idx + 1, tmp, numbers);   
    }
}

int solution(vector<int> numbers, int target) {
    
    numbers_size = numbers.size();
    target_num = target;
    
    dfs(0, 0, numbers);
    
    return answer;
}