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

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

프로그래머스

 

 

풀이

원소 중 3개를 택해 합이 0이 되는지 확인하면 되는 문제.

브루트포스와 DFS 두 가지 방법으로 풀어보았다.

 

 

브루트포스 코드

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

int solution(vector<int> number) {
    int answer = 0;
    
    for(int i=0; i<number.size() - 2; i++){
        for(int j=i + 1; j<number.size() - 1; j++){
            for(int k=j + 1; k<number.size(); k++){
                if(number[i] + number[j] + number[k] == 0) answer++;
            }
        }
    }
    return answer;
}

 

DFS 코드

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

int answer = 0;

void DFS(int idx, int depth, int sum, vector<int>& number){
    if(depth == 3){
        if(sum == 0) answer++;
        return;
    }
    
    for(int i=idx + 1; i<number.size(); i++){
        DFS(i, depth + 1, sum + number[i], number);
    }
}

int solution(vector<int> number) {
    for(int i=0; i<number.size() - 2; i++){
        DFS(i, 1, number[i], number);
    }
    
    return answer;
}