프로그래머스 43165 - 타겟 넘버 (c++)

프로그래머스 43165 - 타겟 넘버

문제 링크

생각 및 접근

• 문제를 보자마자 아주 전형적인 DFS 문제구나. 라고 딱 떠올랐다.
  • DFS에 대한 설명은 (링크)를 참조.
• DFS의 포인트는
  • DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가 ,
  • DFS의 초깃값을 어떻게 잡을 것인가 ,
  • 언제 DFS를 멈추게 할 것인가 ,
  • DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가
    로 나눠볼 수 있겠다.

DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가

• DFS 탐색할 때 depth == numbers.size()까지 탐색해야 하므로 파라미터 level을 넘길 것이다.
• DFS 탐색할 때 (DFS 결과 총 합) == target이 되면 answer++해주어야 하므로 DFS 결과 총 합을 나타내는 파라미터 result를 넘길 것이다.

DFS의 초깃값을 어떻게 잡을 것인가

dfs(0, 0);

언제 DFS를 멈추게 할 것인가

if(level == nums.size()){
    // ...
}

DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가

// + 하는 경우
dfs(level + 1, result + nums[level]);
// - 하는 경우
dfs(level + 1, result - nums[level]);

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> nums;
int answer = 0, tar;

void dfs(int level, int result){
    if(level == nums.size()){
        if(result == tar){
            answer++;
        }
    }
    else{
        dfs(level + 1, result + nums[level]);
        dfs(level + 1, result - nums[level]);
    }
}

int solution(vector<int> numbers, int target) {
    tar = target;
    nums = numbers;

    dfs(0, 0);
    return answer;
}

채점 결과