알고리즘 :: 백준 :: Bruteforce :: 1748 :: 수 이어 쓰기 1

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

문제접근

• 어렵지 않은 문제다. 이 문제를 무작정 1부터 N까지 숫자를 이어붙히는 식으로 계산하면 정말 오래걸린다. 즉, N = 120이라고 할 때, 1+1+...1+2+2+2+....3+3+3...으로 계산하고 있으면 안된다는 소리다.
• 가장 직관적인 방법은 자릿수로 나눠서 풀이하는 방법이다.
• 1~9까지는 길이가 1, 10~99까지는 길이가 2, 100~999까지는 길이가 3이므로 N의 자릿수를 계산하는 것이 문제의 핵심이다.

코드

#include <iostream>
#include <cmath>
using namespace std;

int N;
// N의 자릿수를 구하는 함수
int getStandingNum() {
	int ret = 1;
	while(true) {
		if (N < pow(10, ret)) break;
		ret++;
	}
	return ret;
}
int main( ) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	
	int alpha = getStandingNum();	// 자릿수를 구한다.
	long long ans = 0;				// long long 타입을 사용해야 한다.
	while (alpha > 0) {
		ans += ((N - pow(10, alpha - 1) + 1) * alpha);	// alpha 자릿수인 숫자 개수
		N -= (N - pow(10, alpha - 1) + 1);				// N의 자릿수를 낮춰준다.
		alpha--;	// 자릿수를 낮춘다.
	}
	cout << ans << '\n';
}

결과