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

https://programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 

코딩테스트 연습 - 타겟 넘버

Level 2 DFS

일련의 자연수를 담은 배열이 하나 주어지고, 이들을 적절히 더하고 빼서 target과 동일해지는 경우의 수가 몇인지 반환하는 문제

 

접근방법

하나의 숫자 당 양수, 음수 두 가지 경우를 고려한다.

DFS에 적용해보면, 하나의 수에 대해 양수/음수가 각각 하나의 노드인 셈이다.

각 노드의 인접한 노드들은 배열의 바로 다음번 요소의 양수/음수 이다.

탐색이 단방향으로 진행될 것이고, 이미 방문했던 노드를 방문할 경우가 없기 때문에

방문 여부를 담은 자료구조는 사용하지 않았다.

 

오답노트

오답은 아니고

원래 코드는 dfs를 사용하던 방식대로

노드들을 한번 순회한 결과 값(이번 경우엔 노드를 방문하면서 각 노드의 값을 더하거나 빼야 하므로 누적 계산 결과)을 담을 변수(sum 변수)를 선언했다.

그리고 dfs함수 안에서 sum변수를 갱신하고(방문 노드 값 더하기/빼기), dfs함수를 재귀적으로 호출한 후에 sum변수 갱신을 취소했다. (더했으면 빼고, 뺐으면 더함)

그럴 필요 없이 dfs 함수의 매개변수로 요소값이 아닌 결과값(sum)을 받고, 호출할 때 인자에 sum + 이번에 방문할 노드의 값 을 넣어주면 된다.

그러면 sum 값이 변한 것은 아니므로 갱신을 취소하는 동작을 하지 않아도 된다.

 

아래에 두 코드를 모두 첨부했다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int count = 0;
int result = 0;
int globalTarget;
vector<int> globalNumbers;

void dfs(int sum, int i){
    if(i == globalNumbers.size()-1){
        if(sum == globalTarget)
            count++;
        return;
    }
    dfs(sum + globalNumbers[i+1], i+1);
    dfs(sum - globalNumbers[i+1], i+1);
}

int solution(vector<int> numbers, int target) {
    globalNumbers = {numbers.begin(), numbers.end()};
    globalTarget = target;
    
    dfs(numbers[0], 0);
    dfs(-numbers[0], 0);
    return count;
}

#include <string>
#include <vector>
using namespace std;

int count = 0;
int result = 0;
int globalTarget;
vector<int> globalNumbers;

void dfs(int n, int i){
    result += n;
    
    if(i == globalNumbers.size()-1){
        if(result == globalTarget)
            count++;
        return;
    }
    
    dfs(globalNumbers[i+1], i+1);
    result -= globalNumbers[i+1];
    
    dfs(-globalNumbers[i+1], i+1);
    result += globalNumbers[i+1];
}

int solution(vector<int> numbers, int target) {
    globalNumbers = {numbers.begin(), numbers.end()};
    globalTarget = target;
    
    dfs(numbers[0], 0);
    result -= numbers[0];
    dfs(-numbers[0], 0);
    
    return count;
}