1748번: 수 이어 쓰기 1

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있습니다.

123456789101112131415...

이렇게 만들어진 새로운 수는 총 몇 자리 수인지 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 N (1 ≤ N ≤ 100,000,000)이 주어집니다.
• 출력: 첫째 줄에 새로운 수의 자릿수를 출력합니다.

링크: https://www.acmicpc.net/problem/1748

풀이: 자릿수의 기여도(Contribution)를 활용한 수학적 최적화

N이 최대 1억이므로 1부터 N까지 순회하며 문자열을 이어 붙이거나 자릿수를 일일이 더하면 무조건 시간 초과가 발생합니다. 이 코드는 '각 숫자가 전체 자릿수에 몇 번 기여하는가?'를 수학적으로 분해하여 단 몇 번의 연산만으로 정답을 도출하는 극도로 최적화된 방식입니다.

예를 들어 N이 120일 때, 자릿수의 총합은 다음과 같이 생각할 수 있습니다.

1. 1의 자리 기여: 1부터 120까지의 모든 숫자(120개)는 최소한 1자리 이상을 가지고 있습니다. 
2. 10의 자리 기여: 10부터 120까지의 숫자(120 - 9 = 111개)는 10의 자리를 추가로 하나 더 가지고 있습니다.
3. 100의 자리 기여: 100부터 120까지의 숫자(120 - 99 = 21개)는 100의 자리를 추가로 하나 더 가지고 있습니다.

결과적으로 120 + (120 - 9) + (120 - 99) = 252라는 정답이 단 3번의 덧셈만으로 도출됩니다.

• 반복문 변수 설정: 뺄셈을 위한 기준값 base를 0으로 시작하여 9, 99, 999... 순서로 증가시킵니다. (base = base * 10 + 9)
• 누적 덧셈: 현재 기준값 base가 N보다 작을 때만 해당 자릿수의 기여도가 발생하므로, ans += n - base를 통해 추가되는 자릿수만큼 정답에 누적합니다.

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int ans = 0;
        
        // base: 0 -> 9 -> 99 -> 999 순으로 증가
        int base = 0; 
        
        // n이 base보다 클 때만 해당 자릿수의 숫자가 존재함
        while (base < n) {
            // 해당 자릿수 이상을 가진 숫자들의 개수만큼 자릿수 누적
            ans += n - base;
            
            // 다음 자릿수 검사를 위해 base 갱신
            base = base * 10 + 9;
        }

        bw.write(ans + "");

        bw.flush();
    }
}

알고리즘 분류

수학 (Mathematics), 구현 (Implementation)