[백준 1748] 수 이어 쓰기 1 (C#, C++) - soo:bak

문제 링크

1748번 - 수 이어 쓰기 1

설명

1부터 N까지의 모든 정수를 순서대로 이어붙여 만든 문자열의 총 자릿수를 구하는 문제입니다.

예를 들어,
N = 15일 때 이어붙인 수는 123456789101112131415로, 총 자릿수는 21입니다.

N의 범위가 최대 100,000,000이므로, 단순히 반복문으로 문자열을 만들어 세는 방식은 시간 초과가 발생합니다.

따라서, 자릿수별 패턴을 활용해 효율적으로 계산해야 합니다.

접근법

1. 자릿수별 패턴 분석:
   • 숫자는 자릿수에 따라 구간으로 나뉩니다:
   • 1자리 수: 1 ~ 9 (9개, 각 1자리)
   • 2자리 수: 10 ~ 99 (90개, 각 2자리)
   • 3자리 수: 100 ~ 999 (900개, 각 3자리)
   • ...
   • 길이가 i인 수는 \(9 \times 10^{i-1}\) 개이며, 각 수는 i자리입니다.
     • 따라서 해당 구간의 총 자릿수는:
     \[9 \times 10^{i-1} \times i\]
2. N까지의 자릿수 계산:
   • N이 속한 자릿수 d를 구합니다 (예: \(N=120 \implies d=3\)).

   • 1자리부터 d - 1자리까지는 전체 구간을 계산:

     \[9 \times 10^{i-1} \times i\]

   • 마지막 구간(d자리)은 N까지의 수만 계산:

     • 마지막 구간의 수 개수 : (구간의 끝 - 구간의 시작 + 1)
     \[\text{마지막 구간의 수 개수} = N - 10^{d-1} + 1\]
     • 마지막 구간의 총 자릿수 : (마지막 구간의 수 개수) x (속한 구간의 자릿수 d)
     \[\text{자릿수 기여} = \left( N - 10^{d-1} + 1 \right) \times d\]
3. 구현:
   • N의 자릿수 d를 계산
   • 1 ~ (d - 1)자리 구간의 자릿수를 누적
   • d자리 구간의 자릿수를 추가하여 최종 결과 출력

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    int d = n.ToString().Length;
    long res = 0;

    for (int i = 1; i < d; i++) {
      res += 9L * (long)Math.Pow(10, i - 1) * i;
    }

    res += (long)(n - (int)Math.Pow(10, d - 1) + 1) * d;
    Console.WriteLine(res);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  int d = 0, t = n;
  while (t)
    d++, t /= 10;

  ll ans = 0;
  for (int i = 1; i < d; i++)
    ans += 9LL * pow(10, i - 1) * i;
  ans += 1LL * (n - pow(10, d - 1) + 1) * d;

  cout << ans << "\n";

  return 0;
}