백준 알고리즘 1748. 수 이어쓰기

원본문제 링크

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

1748번: 수 이어 쓰기 1

 

만약 1 2 3 4 5 6 7 8 9 10 11 12 ...

이렇게 숫자를 계속 써내려갈때 1부터 100까지의 숫자를 하나하나씩 센다면

숫자 갯수는 총 몇개일까요?

예를 들면 12라는 숫자는 1과 2를 각각 세어서 2개로 셉니다.

​

그러면 총 192개입니다. 어떻게 그렇게 되냐구요??

0~9 : 9개

10~99 : 90개 X 2자리 = 180개

100 : 1개 X 3자리 = 3개

모두 합치면 192개가 딱 나오지요.

​

그렇다면 1부터 12345까지 이런 식으로 센다면 숫자 갯수는 몇개나 될까요?

컴퓨터 없이도 구하실 수는 있는데요.

댓글로 답변 주시는 분께는 선물을 드리고 싶지만..

여건상 생략하도록 하겠습니다 :)

( 야유의 소리가 들려오네요.. )

​

이 규칙으로 나올수 있는 숫자 갯수를 컴퓨터로 프로그램을 짜서

어떤 숫자가 주어지더라도 모두 세면 되는 문제입니다.

근데 사실 문제 내용을 잘 보면 쉬운 문제가 아닙니다.

왜냐하면 숫자가 만만치 않거든요.

1부터 시작해서 최대값이 무려 100,000,000 까지입니다.

​

컴퓨터에게 하나씩 세도록 하면 어떻게 될까요?

크레이는 해보지 않았지만 아마도 날이 새지 않을까 생각됩니다 :)

​

하지만 이 문제는 어떤 숫자가 주어지더라도 1초 안에 통과를 해야 하는데요.

​

그렇다면 뭔가 아이디어를 좀 생각해야 합니다.

​

크레이는 아래와 같은 아이디어를 생각했습니다만,

더 좋은 아이디어가 있을 수도 있지만 그걸 생각해내는 것은 여러분의 몫으로 돌리도록 하겠습니다 :) 코딩과는 무관하게 대략적인 방법을 댓글주셔도 좋습니다 ㅎㅎ

​

크레이가 생각한 아이디어는 아래와 같은데,

이해를 위해 실례를 들어보겠습니다.

​

1부터 2,234 까지를 센다고 치면,

우선 1~9까지는 9개입니다.

10~99까지는 90개 X 2자리입니다.

100~999까지는 900개 X 3자리 = 2700 개 입니다.

​

여기까지 세고 나서 1000~2234까지는 숫자가 몇개일까요? 자릿수 말고요.

1234개라고 답하신 분은 떙, 1235개입니다 :)

어떻게 그렇게 되냐구요?

1000 ~ 1001까지 숫자를 세어 보시면 이해가 되실 겁니다 :)

이 경우 숫자가 2개이지요.

2234 - 1000 에서 1을 다시 더해줘야 하지요

​

1000 ~ 2234까지는 모두 숫자가 4자리입니다.

그러니까 ( 2234 - 1000 + 1 ) X 4자릿수가 되는 것이지요.

​

그러면 숫자는 7829개가 되지요.

​

해당 소스를 싣습니다.

소스를 설명하려고 들면 사실 본문이 너무 길어져서 그냥 알고리즘을 설명하는 선에서 마칩니다.

필요하신 경우 부분적으로 질문 주시면 답변 드리도록 하겠습니다 :)

감사합니다.

 

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstring>
void Result()
{
	long n;
	scanf("%ld", &n);
	// 최대 100,000,000

	// 예) 2,234 인 경우
	//  A: 0 ~ 999 : 0~9(9개) 10~99 (90개) 100+999(900개)
	//  B: 1000 ~ 2234 (1235개)
	char s[15];
	sprintf(s, "%ld", n);
	int size=strlen(s);

	// 최상단 자릿수를 제외한 나머지 B
	long n2;
	n2 = n - pow((long double)10L, size-1) + 1;
	
	int cnt=n2 * size;

	for(int i=1;i<size;++i)
	{
		cnt+=9*pow((long double)10L, size-i-1) * (size-i);
	}
	printf("%d", cnt);

}

int main()
{
	Result();
	getchar(); getchar();
	return 0;
}