[Programmers] 삼총사 - Java

문제

프로그래머스

 

풀이

삼총사가 되는 경우의 수를 구하는 문제이다.

삼총사는 3명의 학생의 번호를 합했을 때 0이 되는 경우이다.

 

이 문제는 간단하게 3중 for문을 이용하면 풀 수 있다. 

하지만, 3명이 아니라 5명, 10명이라면 5중 10중 for문을 사용할 수는 없다.

 

그래서 for문이 아닌, 재귀적인 방법으로 이 문제를 해결했다.

 

1. 전역 배열을 만들어서 복사한다.

 

2. dfs를 이용해서 3명의 학생 번호를 더한 다음, 삼총사가 되는 경우의 수를 센다.

 

3. 경우의 수를 리턴한다.

 

소스코드

class Solution {
    int answer;
    int[] arr;
    
    public int solution(int[] number) {
        arr = number;
        answer = 0;
        
        for (int i = 0; i < arr.length; i++) {
            backTrack(i, arr[i], 1);
        }
        
        return answer;
    }
    
    void backTrack(int idx, int sum, int depth) {
        if (depth == 3) {
            if (sum == 0) {
                answer++;
            }
            
            return;
        }
        
        for (int i = idx + 1; i < arr.length; i++) {
            backTrack(i, sum + arr[i], depth + 1);
        }
    }
}

 

실행결과