BOJ_1748

문제

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

1234567891011121314151617181920212223...

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

입력

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

출력

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

접근방식

1. 바로 떠오른 접근은 아래와 같다.

int main(void){
	int n; scanf("%d",&n);
	std::string str = "";
	for (int i = 1; i <= n; i++) str += std::to_string(i);
	printf("%lu",str.length());
}

1부터 N까지 가는 반복문이 있고 과정마다 형 변환을 해서 str변수에 더해준다. 그리고 str의 길이를 출력한다.
당연히 메모리 초과... 시간제한도 0.15초고 N도 1억까지 범위를 갖고 있다. 위 방식으로 하면 안된다.

2. 수학적 접근.

1234567891011121314151617181920212223...

이거를 써먹어 보자.
한 자리 숫자가 9개, 두 자리 숫자는 90개, 세자리 숫자는 900개 •••
뭔가 규칙이 보인다.
1=(한 자리 수) x 9개(1~9) = 9
2=(두 자리 수) x 90개(10~99) = 180
3=(세 자리 수) x 900개(100~999) = 2700 이런식으로 개수가 늘어간다.

그렇다면... 예를 들어 N으로 120이 들어왔다고 해보자.
120은 세 자리 수니가 1,2 자리 수는 신경 쓰지 말고 (그냥 더 해주면 되니까)
100~999에서 120이 몇번째에 위치하는지만 알면 문제를 풀 수 있을거 같다!!

쉽다. (120 - 100 + 1)을 해주고 3자리 수니까 3을 곱해주면 끝이다.
답은 9 + 180 + 63 = 252

이거를 이제 코드로 변경해주면 된다.

#include <cstdio>
long long myfunc(long long n ,long long i , long long t){
	if(n == 1) return 1;
	if(t == 0) return 0;
	return (n - i + 1) * t + myfunc(i - 1,i/10,t - 1);
}
int main(void){
	long long n,i=1,t=0; scanf("%lld",&n);
	while(i <= n) {
		t++;//N이 몇 자리 수인지
		i *= 10;
	}
	printf("%lld",myfunc(n,i/10,t));

더 간결하고 쉽게 푼 사람들 무지하게 많다...
다른 사람의 코드를 보는 것 또한 알고리즘 공부 과정 중 하나...