https://www.acmicpc.net/problem/1174
1174번: 줄어드는 수
음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는
www.acmicpc.net
📌 작성한 코드
// 1174
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim();
const N = Number(input);
let list = new Set([]);
const backTracking = (num, count) => {
if (count === 10) {
if (!list.has(num)) list.add(num);
return;
}
backTracking(num, count + 1);
backTracking(num * 10 + 9 - count, count + 1);
};
backTracking(0, 0);
const sorted = [...list].sort((a, b) => a - b);
if (N <= list.size) {
console.log(sorted[N - 1]);
} else {
console.log(-1);
}
📌 설명
줄어드는 수 중 가장 큰 수는 9876543210 -> 10자리의 숫자이다.
그러므로 숫자의 길이가 10 초과인 수가 나올 수 없으니 길이가 10 이하인 숫자만 구하면 답을 구할 수 있다.
백트래킹으로 줄어드는 수 선택하기
- 수를 선택할 때 두가지 갈림길이 존재한다. 현재 숫자를 선택하지 않는 것과, 현재 숫자를 선택해서 숫자의 뒤의 추가하는 것.
(1) 현재 숫자를 선택하지 않기 : count를 증가시켜 숫자의 길이만 증가시키고, 숫자는 그대로 둔다
- ex) 현재 숫자가 43이고 count가 8이라면 432 이렇게 추가하는 것이 아니라 43을 그대로 두고 count만 9로 증가시킨다.
(2) 현재 숫자 선택하기 : 숫자에 10을 곱해서 자리수를 증가시키고, 맨 마지막에 현재 숫자를 더해서 새로운 줄어드는 수를 구한다.
const backTracking = (num, count) => {
if (count === 10) {
if (!list.has(num)) list.add(num); // 자리수가 10이 되면 숫자 있는지 확인하고 추가
return;
}
backTracking(num, count + 1); // 새로운 숫자 선택 안하기
backTracking(num * 10 + 9 - count, count + 1); // 새로운 숫자 선택하기
};
이렇게 모든 줄어드는 수를 구한 뒤에 숫자를 정렬해서, N번째에 해당하는 줄어드는 수를 출력한다.
const sorted = [...list].sort((a, b) => a - b);
if (N <= list.size) {
console.log(sorted[N - 1]);
} else {
console.log(-1);
}
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DP] 백준 골드 5 : 2666 - 벽장문의 이동 (2) | 2024.03.19 |
|---|---|
| [JavaScript] 백준 골드 5 : 5582 - 공통 부분 문자열 (1) | 2024.03.18 |
| [JavaScript/DP] 백준 골드 5 : 2294 - 동전 2 (1) | 2024.03.09 |
| [JavaScript/DP] 백준 골드 5 : 9084 - 동전 (0) | 2024.03.08 |
| [JavaScript/DP] 백준 골드 5 : 9251 - LCS (0) | 2024.03.07 |