IF - 수들의 조합
문제
N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수
는 몇 개가 있는지 출력하는 프로그램을 작성하세요.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을
찾으면 4+8+12 2+4+12로 2가지가 있습니다.
예시
K : 3
numbers : [2, 4, 5, 8, 12]
M : 6
풀이
- 지난 순열 풀이들과 달리 이번에는 조합을 구하는 문제이다.
- 순열은 [2, 4, 5, 8, 12] 에서 3개를 뽑아야 할 때 [2, 4, 5] , [2, 5, 4] 가 원소는 같지만 순서가 다르므로 서로 다른 나열로 보지만, 조합은 배열 내 원소들이 같으므로 이 둘을 같은 나열로 본다.
const DFS = (L, S) => {
if (L === k) {
const sum = temp.reduce((acc, cur) => acc + cur, 0);
sum % m === 0 && count++;
}
- K 개를 뽑아야 하므로, DFS 의 종료조건은
L === K
이다.L===K
일 때 조합 하나가 나왔다는 뜻이므로, 해당 조합의 원소들의 합이m
의 배수인지 검사한다.
else {
for (let i = S; i < numbers.length; i++) {
temp[L] = numbers[i];
DFS(L + 1, i + 1);
}
}
- DFS 의 인자에
S
가 필요한 이유는, DFS 로 깊이가 깊어질 때마다 for 문을 돌 때 이전 깊이에서 temp 에 넣었던numbers
의 원소를 또 넣으면 안되기 때문이다.
코드
const solution = (numbers, k, m) => {
let count = 0;
const temp = Array.from({ length: k }, () => 0);
const DFS = (L, S) => {
if (L === k) {
const sum = temp.reduce((acc, cur) => acc + cur, 0);
sum % m === 0 && count++;
} else {
for (let i = S; i < numbers.length; i++) {
temp[L] = numbers[i];
DFS(L + 1, i + 1);
}
}
};
DFS(0, 0);
return count;
};
Author And Source
이 문제에 관하여(IF - 수들의 조합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goody/IF-수들의-조합-202czs2p저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)