[프로그래머스] 삼총사 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

BruteForce 방식으로 풀었다.

number 길이가 최대 13이기에

가능한 모든 조합을 탐색하여 풀 수 있다.

 

cnt로 몇개의 번호를 받은 상태인지 상태를 체크하고,

sum으로 총합을 관리한다.

이때 cnt가 3이고 sum이 0이라면 삼총사를 구한것이므로 answer++ 해준다.

cnt가 3인 상태에서 반복문을 돌려봐야 cnt가 4이상이 됨으로 삼총사는 구할 수 없으므로 return으로 종료시켰다.

 

전체 코드

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

void rec(int idx, int cnt, int sum, vector<int>& number, int& answer, int maxSize) {
    if(cnt==3&&sum==0) {
        answer++;
        return;
    }
    
    for(int i=idx+1; i<maxSize; i++) {
        rec(i, cnt+1, sum+number[i], number, answer, maxSize);
    }    
}

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