📍문제 링크
https://www.acmicpc.net/problem/6603
📍알고리즘 분류
- 수학
- 조합론
- 백트래킹
- 재귀
📍문제 풀이
- 주어진 수들의 집합에서 6개를 뽑는 경우의 수를 구하자 (조합)
- 백트래킹으로 조합을 구현할 수 있다
- 테스트 케이스 그룹마다 줄바꿈으로 구분해줘야 한다
📍코드 (JavaScript)
const input = require('fs')
.readFileSync('/dev/stdin')
.toString()
.trim()
.split('\n');
input.pop();
const answer = [];
for (let el of input) {
const group = [];
const result = [];
const isUsed = [];
const [k, ...S] = el.split(' ').map(Number);
const recursive = (depth) => {
if (depth === 6) {
const res = result.join(' ');
group.push(res);
return;
}
for (let i = 1; i <= k; i++) {
if (!isUsed[i]) {
// 오름차순이 깨지면 다음 수(depth가 아님) 로 넘어감
if (depth >= 1 && result[depth - 1] > S[i - 1]) continue;
result[depth] = S[i - 1];
isUsed[i] = true;
recursive(depth + 1);
isUsed[i] = false;
}
}
};
recursive(0);
answer.push(group.join('\n'));
}
// 테스트 케이스 단위마다 줄바꿈 넣어줌
console.log(answer.join('\n\n'));
📍리뷰
- 반복문 안에서 매번 재귀 함수를 정의하지 않고, 바깥에서 한 번에 정의하면 복잡도를 개선할 수 있을 것 같다