문제 푼 날짜 : 2021-08-09

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43165

접근 및 풀이

주어진 numbers vector를 전부 탐색하면서 각 요소들을 하나씩 더하고 빼주었다.
그리고 전부 계산됐을 때, target과 같으면 answer를 +1 해주었다.
DFS,BFS로 각각 구현해보았다.

코드 (DFS)

#include <string>
#include <vector>

using namespace std;

vector<int> Numbers;
int Target, answer;

void dfs(int cnt, int sum) {
    if (cnt == Numbers.size() - 1) {
        if (sum == Target) {
            answer++;
        }
        return;
    }
    dfs(cnt + 1, sum + Numbers[cnt + 1]);
    dfs(cnt + 1, sum - Numbers[cnt + 1]);
}

int solution(vector<int> numbers, int target) {
    answer = 0;
    Numbers = numbers, Target = target;
    dfs(0, numbers[0]);
    dfs(0, -numbers[0]);
    return answer;
}

코드 (BFS)

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

using namespace std;

struct Point {
    int cnt, sum;
};

int solution(vector<int> numbers, int target) {
    int answer = 0;
    bool visited[21] = { false };
    
    queue<Point> q;
    q.push({ 0, numbers[0] });
    q.push({ 0, -numbers[0] });
    
    while (!q.empty()) {
        Point now = q.front();
        q.pop();
        
        if (now.cnt == numbers.size() - 1) {
            if (now.sum == target) {
                answer++;
            }
            continue;
        }
        q.push({ now.cnt + 1, now.sum + numbers[now.cnt + 1] });
        q.push({ now.cnt + 1, now.sum - numbers[now.cnt + 1] });
    }
    return answer;
}

결과

피드백

프로그래머스 level2 문제를 통해 기본기를 다져보자