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

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

프로그래머스

 

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

int answer = 0;
void recur(vector<int> number, int cnt, int num, int index)
{
    if (cnt!=3&&index >= number.size())return;
    if (cnt == 3)
    {
        //cout << "end : " << cnt << ' ' << num << ' ' << index<<endl;
        if (num == 0)
            answer++;
        return;
    }
    num += number[index];
    //cout <<"더함 : "<< cnt + 1 << ' ' << num << ' ' << index + 1 << endl;
    recur(number, cnt + 1, num, index + 1);
    num -= number[index];
    //cout << "더하지않음 : " << cnt<< ' ' << num << ' ' << index + 1 << endl;
    recur(number, cnt, num, index + 1);
}

int solution(vector<int> number) {
    recur(number, 0, 0, 0);
    return answer;
}

 

설명

이 문제는 주어진 배열에서 숫자 3개를 더한 합이 0이 되는 조합의 개수를 찾는 문제이다. 

3중 for문이나 재귀함수로 풀 수 있는데 여기선 재귀로 풀었다. 

 

 

 매개변수는 순서대로 수의 배열, cnt== 더한 수의 개수, num== 수의 합, index == 더해야하는 인덱스 이다. 

재귀함수에서는 반드시 종료조건이 포함되어야한다. 여기서는 index가 범위를 벗어나거나 cnt가 3이되면 종료되도록 했다. 

if (cnt!=3&&index >= number.size())return;

이 조건에서 주의해야할 것은 index만을 비교할게 아니고 cnt가 3이 아니면서 index가 범위를 벗어났을 때 종료해야 된다는 것이다. 단순히 index가 범위를 벗어났을 때 종료하라고 한다면 마지막 숫자를 더했을 때, 그 다음은 index가 범위를 벗어나기 때문에 답이 되는지를 비교하지 않고 종료가 된다. 주의하자. 

 

if (cnt == 3)
    {
        //cout << "end : " << cnt << ' ' << num << ' ' << index<<endl;
        if (num == 0)
            answer++;
        return;
    }

다음으로 이 조건으로  3개숫자의 합이 0이 돼서 답이 되는지를 판단한다. 

 

그리고 재귀되는 구간인 코드이다.

num += number[index];
    //cout <<"더함 : "<< cnt + 1 << ' ' << num << ' ' << index + 1 << endl;
    recur(number, cnt + 1, num, index + 1);
    num -= number[index];
    //cout << "더하지않음 : " << cnt<< ' ' << num << ' ' << index + 1 << endl;
    recur(number, cnt, num, index + 1);

현재 index인 수를 더하거나 더하지 않고 재귀를 실행한다. 

이렇게 해야 모든 경우의 수를 파악할 수 있다.