자릿수 합이 K의 배수인 수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
양의 정수 lo, hi, k가 주어집니다. lo 이상 hi 이하의 정수 중에서, 십진법으로 쓴 각 자릿수의 합이 k의 배수인 수는 몇 개인지 반환하세요.
예를 들어 4817의 자릿수 합은 4 + 8 + 1 + 7 = 20이므로 k = 5일 때 조건을 만족합니다.
입출력 예
| lo | hi | k | result |
|---|---|---|---|
1 | 20 | 3 | 6 |
10 | 99 | 10 | 9 |
7 | 7 | 2 | 0 |
입출력 예 설명
예 1 — 3, 6, 9, 12, 15, 18의 6개입니다. 자릿수 합이 3의 배수인 수는 곧 3의 배수입니다.
예 2 — 두 자리 수 중 자릿수 합이 10인 19, 28, 37, 46, 55, 64, 73, 82, 91의 9개입니다. (자릿수 합은 최대 18이라 20은 될 수 없습니다.)
예 3 — 7의 자릿수 합 7은 짝수가 아닙니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(lo: long, hi: long, k: int) → long
제한 사항
-
lohi -
k - 답은 64비트 정수 범위 안입니다.
기대 복잡도
- 시간
- O(D * K * 10)
- 공간
- O(D * K)
입출력 예
| lo | hi | k | 기대 출력 |
|---|---|---|---|
1 | 20 | 3 | 6 |
10 | 99 | 10 | 9 |
7 | 7 | 2 | 0 |
힌트
힌트
범위가 까지라 수를 하나씩 확인할 수는 없습니다. 자릿수 DP를 쓰세요.
먼저 f(N) = "0 이상 N 이하에서 조건을 만족하는 수의 개수"를 구하면 답은 f(hi) - f(lo - 1)입니다.
f(N)은 N의 자릿수를 앞에서부터 정해 가며 셉니다. 상태는
- 지금까지 정한 자릿수의 합을
k로 나눈 나머지, - 지금까지의 자릿수가
N의 앞부분과 똑같은지(그렇다면 다음 자릿수는N의 해당 자릿수까지만 쓸 수 있음)
입니다. N과 같은 길로 가지 않고 한 번이라도 더 작은 숫자를 고르면, 남은 자리는 0~9를 자유롭게 쓸 수 있습니다.
ways[r][m] = "남은 r자리를 자유롭게 채워 자릿수 합의 나머지를 m으로 만드는 방법 수"를 미리 계산해 두면 편합니다.
복잡도 목표
lo부터 hi까지 모든 수의 자릿수 합을 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 자릿수 개수 에 대해 정도면 충분합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 13 | 판정만 |
| performance | 60 | 6 | 판정만 |