[BF] 1748번 수 이어 쓰기1

1748번 수 이어 쓰기1

 

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

 

문제

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

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1≤N≤100,000,000)이 주어진다.

 

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

 

예제 입력

120

 

예제 출력

252

 

해결방법

브루트포스 문제이다.

사실 처음에는 모든 N의 경우를 전부 해봤었다. 결과는 당연히 시간초과였다.

따라서 시간초과를 해결할 솔루션을 생각해내야 했다.

 

⭐️솔루션⭐️

먼저 각 자리수 별로의 수의 개수를 파악한다

범위	개수
1~9	9개
10~99	90개
100~999	900개
1000~9999	9000개

 

🌈 만약 n의 자리수가 4자리면 1~3자리까지 모든 수는 포함된다

각 자리수 별로 수의 개수 * 자리 수 를 ans 에 더해준다

num = 9;
ans = 0;
for(int i=1; i<s; i++){
    ans += (num*i);
    num *= 10;
}

 

🌈 4자리 수인 경우는 n - 1000 + 1 이다

num /= 9;
num = n - num + 1;
ans += (s*num);

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 0
#define INF 987654321
using namespace std;

int n;
int s;
int ans,num;

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    s = (int) to_string(n).size();
    
    num = 9;
    ans = 0;
    for(int i=1; i<s; i++){
        ans += (num*i);
        num *= 10;
    }
    num /= 9;
    num = n - num + 1;
    ans += (s*num);
    
    cout << ans << endl;
}