C++ / 프로그래머스 / 삼총사

문제

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

프로그래머스

 

문제풀이

현재 위치, 고른 개수, 번호의 합을 인자로 받는 DFS함수를 만들어서 풀었다.

3개를 골랐으면 세 명의 번호 합이 0인지 판별하고 맞으면 답을 출력하는 변수에 1을 더한다.

현재 위치가 끝나지 않았으면 DFS(x+1, cnt, sum)을 해서 현재 학생을 포함 안 하는 경우를,

DFS(x+1, cnt+1, sum+num[x])을 해서 현재 학생을 포함하는 경우를 탐색한다.

 

코드

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

vector<int>num;
int answer;

void DFS(int x, int cnt, int sum) {
    if (cnt == 3) {
        if (sum == 0)
            answer++;
    }
    else if (x < num.size()) {
        DFS(x + 1, cnt, sum);
        DFS(x + 1, cnt + 1, sum + num[x]);
    }
}

int solution(vector<int> number) {
    num = number;
    DFS(0, 0, 0);
    return answer;
}