BOJ 1748. 수 이어 쓰기 1

Problem Solving

게시 2020/04/01 수정 2026/10/07 작성자 August

조회 5 분 읽는 시간

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

문제 요약

1부터 N까지 각 수의 자릿수를 모두 더한 값을 구하는 문제다. 이어 쓴 수를 실제로 만들 필요는 없고, 길이만 알면 된다.

1. 문제 해석

N이 너무 크기 때문에, 실제로 수를 만드는 것은 너무 시간이 오래 걸린다.
총 N개의 수를 하나의 문자열로 만들어야 한다.
O(N) × 10 -> 최대 1억 번
여기서 10은 수의 최대 자릿수를 의미한다.

수를 하나씩 문자열로 바꿔 이어 붙이면, N개의 수마다 자릿수만큼 문자를 다뤄야 한다. 문자열을 실제로 만들면 메모리도 그 길이만큼 필요하다. 수를 하나씩 보지 않고 묶어서 셀 방법이 필요하다.

1 2 3 4 5 6 7 8 9 / 10 11 12 13 14 15 16 17 18 19 20 21 22 23 … 99 / 100 101 … 999 … 일단 1부터 N까지의 수를 나열해보면, 한 자리 수는 9개이고, 두 자리 수는 99-10+1 개이고, 세 자리 수는 999-100+1 개 이다.

즉, 수의 자리수별로 나누어서 문제를 해결할 수 있다.

N = 120 이면
1 - 9 → (9-1+1) × 1
10 - 99 → (99-10+1) × 2
100 - 120 → (120-100+1) × 3

값을 계산하면 9 + 180 + 63 = 252다.

왜 자릿수별로 묶으면 되는가

같은 자릿수를 가진 수는 연속된 구간을 이룬다. k자리 수는 정확히 10^(k-1)부터 10^k - 1까지다. 그래서 각 구간에 속한 수의 개수에 k를 곱하면 그 구간이 만드는 문자 수가 된다. N이 속한 마지막 구간만 끝을 10^k - 1 대신 N으로 자르면 된다.

구간의 수는 N의 자릿수와 같으므로, 반복 횟수는 N이 아니라 N의 자릿수(약 log10 N)에 비례한다.

2. 문제 풀이

  
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int start=1, len=1; start<=n; start*=10, len++) {
        int end = start*10-1;
        if (end > n) { // N=120인 경우 999>120 이므로, 예외처리
            end = n;
        }
        ans += (long long)(end - start + 1) * len;
    }
    cout << ans << '\n';
    return 0;
}

코드 따라가기

start는 현재 구간의 첫 수(1, 10, 100, …), len은 그 구간의 자릿수다. 반복할 때마다 start는 10배, len은 1씩 커진다.
end = start*10-1은 같은 자릿수의 마지막 수(9, 99, 999, …)다.
end > n이면 N이 이 구간 안에 있다는 뜻이므로 끝을 N으로 자른다. 이 구간이 마지막이고, 다음 반복에서 start가 N을 넘어 반복이 끝난다.
(end - start + 1) * len이 구간의 문자 수다. 곱셈 전에 long long으로 바꿔 두어 결과가 커져도 넘치지 않게 했다.

N = 120으로 따라가면 다음과 같다.

start	len	end	더하는 값	누적
1	1	9	9 × 1 = 9	9
10	2	99	90 × 2 = 180	189
100	3	999 → 120	21 × 3 = 63	252
1000			반복 종료

start와 end를 int로 두었으므로 start*10이 int 범위(약 21억)를 넘지 않아야 한다. start는 N 이하인 동안만 10배가 되므로, N이 10억보다 작다면 start*10의 최댓값도 int 범위 안에 있다.

복잡도

시간: O(log N). 자릿수 구간마다 한 번씩 반복한다.
공간: O(1). 문자열을 만들지 않는다.

참고한 자료외부 출처 1

외부 출처

BOJ 1748 수 이어 쓰기 1Baekjoon Online Judge

ProblemSolving, BOJ