Funcia
Lv.3digit-dpdpmath

자릿수 합이 K의 배수인 수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

양의 정수 lo, hi, k가 주어집니다. lo 이상 hi 이하의 정수 중에서, 십진법으로 쓴 각 자릿수의 합이 k의 배수인 수는 몇 개인지 반환하세요.

예를 들어 4817의 자릿수 합은 4 + 8 + 1 + 7 = 20이므로 k = 5일 때 조건을 만족합니다.

입출력 예

lohikresult
12036
1099109
7720

입출력 예 설명

예 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

제한 사항

  • 1≤1 \le lo ≤\le hi ≤1018\le 10^{18}
  • 1≤1 \le k ≤200\le 200
  • 답은 64비트 정수 범위 안입니다.

기대 복잡도

시간
O(D * K * 10)
공간
O(D * K)

입출력 예

lohik기대 출력
12036
1099109
7720

힌트

힌트

범위가 101810^{18}까지라 수를 하나씩 확인할 수는 없습니다. 자릿수 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까지 모든 수의 자릿수 합을 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 자릿수 개수 D≤19D \le 19에 대해 O(D⋅K⋅10)O(D \cdot K \cdot 10) 정도면 충분합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4013판정만
performance606판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.