문제
L 이상 U 이하의 모든 정수의 각 자리 숫자의 합을 구하라.
입력
첫째 줄에 두 정수 L과 U가 주어진다 (0 이상 2,000,000,000 이하).
출력
모든 정수의 각 자리 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
0 3 | 6 |
10 14 | 15 |
풀이
양쪽 끝에서 10의 배수 경계까지 처리하고, L과 U를 10으로 나누며 자릿수 단위로 합산한다.
- L이 10의 배수가 될 때까지 L의 각 자리를 delta 가중치로 cnt 배열에 누적하며 L을 증가시킨다
- U가 10의 배수-1이 될 때까지 U의 각 자리를 delta 가중치로 cnt 배열에 누적하며 U를 감소시킨다
- 남은 구간의 L, U를 10으로 나누고, 0~9 각 숫자가 동일 횟수만큼 등장하므로 일괄 처리한다
- delta를 10배씩 증가시키며 반복하고, 최종적으로 cnt[i] * i를 합산한다
핵심 아이디어: 자릿수 DP의 변형으로, 구간 양 끝을 10의 배수 경계로 맞춘 뒤 자릿수를 줄여가며 O(D * 10) 시간에 해결한다 (D는 자릿수).
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day188BOJ1081구간합 { // 1081 합 구간합
static long L, U;
static long[] cnt;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
U = Integer.parseInt(st.nextToken());
cnt = new long[10];
long delta = 1;
while (L <= U) {
for (; L % 10 != 0 && L <= U; L++) {
parse(L, delta);
}
for (; U % 10 != 9 && L <= U; U--) {
parse(U, delta);
}
if (L > U)
break;
L /= 10;
U /= 10;
long rowCnt = U - L + 1;
for (int i = 0; i < 10; i++) {
cnt[i] += delta * rowCnt;
}
delta *= 10;
}
long ans = 0L;
for (int i = 0; i < 10; i++) {
ans += i * cnt[i];
}
System.out.println(ans);
br.close();
}
static void parse(long x, long delta) {
while (x > 0) {
cnt[(int) x % 10] += delta;
x /= 10;
}
}
}복잡도
- 시간: O(D * 10) - D는 자릿수 (최대 10)
- 공간: O(1) - cnt 배열 크기 10 고정