자릿수 DP(조건 만족 개수) 계산기
1부터 N까지 중 자릿수 조건을 만족하는 수가 몇 개인지 자리를 앞에서부터 채워 가며 셉니다. 상한 제약을 «지금까지 N과 똑같이 왔는가»라는 상태 하나로 담아내는 것이 이 기법의 전부입니다.
1부터 N까지를 셉니다. 16자리까지 다룹니다.
이 숫자를 하나 이상 포함하는 수
1 ~ 1,000,000 중 숫자 3을(를) 하나 이상 포함
468,559개
자리 7개를 채우며 상태 23개만 방문했습니다. 하나씩 세려면 1,000,000번 봐야 합니다.
자리마다
| 자리 | N의 숫자 | tight일 때 고를 수 | 아닐 때 |
|---|---|---|---|
| 1번째 | 1 | 0 ~ 1 (2가지) | 0 ~ 9 (10가지) |
| 2번째 | 0 | 0 ~ 0 (1가지) | 0 ~ 9 (10가지) |
| 3번째 | 0 | 0 ~ 0 (1가지) | 0 ~ 9 (10가지) |
| 4번째 | 0 | 0 ~ 0 (1가지) | 0 ~ 9 (10가지) |
| 5번째 | 0 | 0 ~ 0 (1가지) | 0 ~ 9 (10가지) |
| 6번째 | 0 | 0 ~ 0 (1가지) | 0 ~ 9 (10가지) |
| 7번째 | 0 | 0 ~ 0 (1가지) | 0 ~ 9 (10가지) |
tight란 «지금까지 N과 똑같이 왔다»는 뜻입니다. 그 자리에서 N의 숫자보다 작은 것을 한 번이라도 고르면 tight가 풀리고, 그 뒤로는 0~9 아무거나 넣어도 N을 넘지 않습니다. 한번 풀리면 다시 붙지 않아 상태가 폭발하지 않습니다.
구간으로 세려면
두 번 세어 빼면 됩니다. 자릿수 DP는 «1부터 N까지»만 셀 수 있게 짜는 편이 훨씬 단순하고, 구간은 이렇게 처리하는 것이 정석입니다.
사용 방법
- 1상한 N을 넣습니다. 안전한 정수 범위(16자리)까지 다룹니다.
- 2세고 싶은 조건을 고릅니다 — 특정 숫자 포함/제외, 자릿수 합, 이웃 조건 등입니다.
- 3조건을 만족하는 수의 개수가 바로 나옵니다.
- 4N이 작으면 1부터 하나씩 세어 본 값이 함께 나와 검산이 됩니다.
- 5구간 [lo, hi]로 세려면 두 번 세어 빼면 되는 것도 함께 보여 드립니다.
자주 묻는 질문
«지금까지 N과 똑같이 왔는가»라는 불리언 하나(tight)가 상한 제약을 통째로 담는다는 것입니다. tight면 지금 자리에 넣을 수 있는 숫자가 0부터 N의 그 자리까지로 제한되고, 이미 N보다 작아졌으면 0~9 아무거나 됩니다. 한번 tight가 풀리면 다시 붙지 않기 때문에 상태가 폭발하지 않습니다.
5를 세 자리로 쓰면 «005»가 되는데, 이 0들을 진짜 숫자로 세면 «숫자 0을 쓰지 않는 수» 같은 조건이 통째로 무너지기 때문입니다. 그래서 «수가 이미 시작됐는가»라는 상태를 하나 더 들고 갑니다. 자릿수 합처럼 0에 영향받지 않는 조건도 있지만, 조건마다 따지는 것보다 늘 들고 가는 편이 안전합니다.
N에 비례하던 것이 자릿수에 비례하게 됩니다. 10억까지 세려면 하나씩은 10억 번이지만 자릿수 DP는 (자릿수 × 상태 수 × 10)번이라 몇백 번이면 끝납니다. 이 계산기는 실제로 방문한 상태 수를 함께 보여 주니 얼마나 줄어드는지 확인해 보십시오.
두 번 세어 빼면 됩니다. f(b) − f(a−1)입니다. 자릿수 DP는 «1부터 N까지»만 셀 수 있게 짜는 것이 훨씬 단순하고, 구간은 이렇게 처리하는 것이 정석입니다. 이 계산기도 그렇게 하고 두 값을 모두 보여 드립니다.
자바스크립트의 수가 2⁵³을 넘으면 입력한 값 자체를 정확히 담지 못하기 때문입니다. 그러면 사용자가 친 수가 아니라 그 근처의 다른 수를 세게 되므로, 애초에 받지 않습니다. 알고리즘 자체는 자릿수만 늘면 되니 입력을 문자열이나 BigInt로 받으면 더 큰 N도 다룰 수 있습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.
알아두면 좋은 점
- 다루는 조건을 여섯 가지로 못 박았습니다. 자릿수를 앞에서부터 보며 유한한 상태로 판단할 수 있는 조건이라면 같은 틀로 얼마든지 늘릴 수 있습니다.
- «나머지가 k인 수» 같은 조건은 자릿수 합이 아니라 수 자체의 나머지를 상태로 들고 가면 됩니다. 상태 수가 나누는 수만큼 늘어납니다.
- 0은 세지 않습니다. 1부터 N까지가 대상입니다.
- 조건 여섯 가지 × N을 0~400과 9990~10010에서 촘촘히, 그리고 20만까지 띄엄띄엄 훑어 하나씩 세어 본 값과 대조했습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.