https://www.acmicpc.net/problem/6603
6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
📌 작성한 코드
// 6603
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const LOTTO_COUNT = 6;
while (true) {
const temp = input.shift();
if (temp === "0") break;
const [k, ...list] = temp.split(" ").map(Number);
let arr = new Array(6).fill(0);
let visited = new Array(list.length).fill(false);
let answer = "";
const backTraking = (at, count) => {
if (count === LOTTO_COUNT) {
answer += `${arr.join(" ")}\n`;
return;
}
for (let i = at; i < k; i++) {
if (!visited[i]) {
arr[count] = list[i];
visited[i] = true;
backTraking(i + 1, count + 1);
visited[i] = false;
}
}
};
backTraking(0, 0);
console.log(answer);
}
📌 설명
숫자를 선택해서 수열을 만드는 경우에는 백트래킹을 이용하면 간단하게 해결할 수 있다.
N과 M 문제 시리즈를 풀어보았다면 간단하게 문제를 해결할 수 있을 것이다.
(1) 제약 조건 확인하기
해당 백트래킹을 할 때 신경 써야 하는 부분은
- 같은 수를 여러번 선택할 수 없다. (로또 번호니까 당연하다)
- 사전순으로 출력해야 한다.(순서가 다른 수열을 생성할 필요가 없다. 사전순으로 정렬된 수열만 생성한다)
(2) 제약 조건 신경써서 코드 작성하기
const backTraking = (at, count) => {
if (count === LOTTO_COUNT) {
answer += `${arr.join(" ")}\n`;
return;
}
for (let i = at; i < k; i++) { // 사전순으로 출력해야 하니까 더 큰 숫자만 선택해야함 -> at으로 관리
if (!visited[i]) // 방문하지 않은 숫자라면 -> 중복을 방지하기 위하여
arr[count] = list[i];
visited[i] = true;
backTraking(i + 1, count + 1); // 현재 보다 큰 숫자부터 접근하도록 i+1
visited[i] = false;
}
}
};
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/백트래킹] 백준 골드 5 : 16987 - 계란으로 계란치기 (1) | 2024.02.08 |
|---|---|
| [JavaScript/백트래킹] 백준 골드 5 : 1759 - 암호 만들기 (1) | 2024.02.04 |
| [JavaScript/백트래킹] 백준 실버 2 : 15663 - N과 M (9) (1) | 2024.02.02 |
| [JavaScript/백트래킹] 백준 실버 3 : 15657 - N과 M (8) (1) | 2024.02.02 |
| [JavaScript/백트래킹] 백준 실버 3 : 15656 - N과 M (7) (0) | 2024.02.02 |