[구현] BOJ 1748 수 이어 쓰기 1

www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

문제 해결 알고리즘

 

이 문제를 숫자들을 나열해서 풀이하려하면 시간초과가 난다.

그러므로 간단한 식을 써서 풀어야하는데, 간단하다.

 

1. 우선 주어진 수 $N$의 자리수를 구한다.

 

2. 결괏값(result)에 자리수 $i$에 대해 1부터 $N-1$의 자릿수까지 각각 $9  \times i \times 10 ^ {i-1}$ 더해준다.

 

3. 마지막으로 자리수 $N$에 해당하는 길이는 입력받은 수(tmp)보다 자리수가 하나 작은 가장 큰 수를 빼준 수에서 $N$만큼 곱해준 걸 결괏값(result)에 더해준다. 

 

소스 코드

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

int main(){
  int N; cin >> N;
  int tmp = N;
  long long cnt = 0, result = 0;

  while(N /= 10) cnt++;

  for(int i=1;i<=cnt;i++) result += 9 * i * pow(10,i-1);

  tmp -= pow(10,cnt) - 1;

  result += tmp * (cnt+1);
  
  cout << result;

}