#1748: 수 이어 쓰기 1

백준 1748번: 수 이어 쓰기 1

문제:

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

1234567891011121314151617181920212223…

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

입력:

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

풀이:

• 처음에 브루트 포스 문제이니 n까지 모든 수의 길이를 다 더할려고 하였지만 시간 초과로 틀렸다. 따라서 좀 더 효율적인 방법으로 풀어야 돼서 각 자리수만큼 더하는 방법을 레바스님의 블로그 포스팅을 통해 알게 되어 풀었다.
• 모든 경우의 수를 다 더하는 것이 아닌 각 자리수마다 해당 되는 숫자만큼 구하는 식 = 입력값-10의 배수+1을 하면 일의 자리수를 모두 더한 뒤 십의 자리수에서는 일의 자리수를 제외한 만큼 더해주면 된다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n, i = 1, answer=0;
	//입력
	cin >> n;
	//10의 배수 i가 입력값보다 클때까지 연산 실행
	while(i <= n){
		//각 자리수를 가지고 있는 수 만큼 더한다 ex) 15 = 일의 자리수 15 + 십의 자리수 6
		answer+=n-i+1;
		i*=10;
	}
	//출력
	cout<<answer;
}