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

타겟 넘버

문제 링크

타겟 넘버

분석

DFS 혹은 BFS로 풀 수 있는 문제입니다.

BFS는 일반적으로 큐를 사용합니다.

저는 DFS로 풀이하려 합니다.
일반적으로 스택 또는 재귀함수를 사용해서 구현합니다.

DFS로 구현된 함수 내부에서 인덱스를 1 증가시키면서, 현재 숫자에 값을 더한 경우와 뺀 경우로 모든 경우의 수를 살펴보아야 합니다.

풀이

#include <vector>

using namespace std;

// 가능한 경우의 수를 저장하는 전역 변수
int answer = 0;

// DFS를 사용한 모든 경우의 수 탐색
// numbers 사용할 숫자 목록
// index 현재 탐색 중인 숫자의 인덱스
// sum 현재까지의 합
// target 목표 숫자
void dfs(const vector<int>& numbers, const int target, int index, int sum)
{
    // 모든 숫자를 탐색한 경우 종료
    if (numbers.size() <= index)
    {
        // 타겟 넘버를 만들 수 있는 경우
        if (sum == target)
        {
            ++answer;
        }
        return;
    }
    
    int nextIndex = index + 1;
 
    // 인덱스를 1 증가시키고, 숫자를 더한 경우와 뺀 경우에 대해 탐색
    dfs(numbers, target, nextIndex,  sum + numbers[index]);
    dfs(numbers, target, nextIndex,  sum - numbers[index]);
}

int solution(vector<int> numbers, int target) {
    // 함수 호출
    dfs(numbers, target, 0, 0);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(2^n)$입니다.

• DFS 함수의 호출 $O(2^n)$

공간 복잡도는 $O(n)$입니다.

• DFS 함수 호출 스택 $O(n)$

테스트 1 〉 통과 (3.83ms, 4.03MB)
테스트 2 〉 통과 (3.69ms, 3.67MB)
테스트 3 〉 통과 (0.01ms, 4.13MB)
테스트 4 〉 통과 (0.02ms, 4.21MB)
테스트 5 〉 통과 (0.12ms, 4.16MB)
테스트 6 〉 통과 (0.01ms, 3.7MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.04ms, 4.21MB)