문제
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
삼총사가 되는 경우의 수를 구하는 문제이다.
삼총사는 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);
}
}
}
실행결과

'Problem Solving > Programmers' 카테고리의 다른 글
| [Programmers] 숫자 문자열과 영단어 - Java (2) | 2025.09.15 |
|---|---|
| [Programmers] 옹알이 (2) - Java (1) | 2025.09.14 |
| [Programmers] 부족한 금액 계산하기 - Java (1) | 2025.08.30 |
| [Programmers] 예산 - Java (0) | 2025.08.29 |
| [Programmers] 문자열 내 p와 y의 개수 - Java (0) | 2025.08.28 |