[Algorithm] 11. 숫자의 총 개수(small, large)

노력하는 호머

인트로

알고리즘 코드는 C 또는 C++ 기반으로 작성되었습니다.

 

 

숫자가 입력되면 1부터 N까지의 숫자까지 총 몇 개의 숫자가 사용되었을지 구하는 문제이다.

숫자가 작으면 간단한 방식으로 해결이 되지만 숫자가 많아지면 시간이 오래 걸리게 된다.

작은 숫자 큰 숫자 모두 잘 돌아가는 코드를 알아보려 한다.

 

숫자의 총 개수 (SMALL)

문제

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자는 몇 개 쓰였을까요?
예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 총 21개가 쓰였음을 알 수 있습니다.
자연수 N이 입력되면 1부터 N까지 각 숫자는 몇 개가 사용되었는지를 구하는 프로그램을 작 성하세요.

※입력 설명
첫 번째 줄에는 자연수 N(3 <=N <100,000)이 주어진다. 

※출력설명
첫 번째 줄에 숫자의 총개수를 출력한다.

입력

15

출력

21

 

생각하기 가장 쉬운 코드이다.

1부터 N까지 for문을 돌리고 숫자의 길이( 사용된 숫자)를 반환하는 함수를 작성하면 된다.

코드가 돌아가는 방식은 이중 for문이다.

N값이 작으면 상관없지만 N이 1억이라고 가정하면 후반부 숫자들은 내부 for문을 8회 반복한다.

반복을 줄이기 위해선 수학적인 안목이 필요하다.

#include <iostream>

using namespace std;

int count_num(int num)
{
	int count = 0;

	while (num > 0)
	{
		num = num / 10;
		count++;
	}
	return count;
}

int main()
{
	int num, count = 0;
	
	cin >> num;

	for (int i = 1; i <= num; i++)
	{
		count += count_num(i);
	}

	cout << count;
}

숫자의 총 개수 (LARGE)

문제

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자는 몇 개 쓰였을까요?
예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 총 21개가 쓰였음을 알 수 있습니다.
자연수 N이 입력되면 1부터 N까지 각 숫자는 몇 개가 사용되었는지를 구하는 프로그램을 작 성하세요.

※입력설명
첫 번째 줄에는 자연수 N(3<=N<=100,000,000)이 주어진다.

※출력설명
첫 번째 줄에 숫자의 총개수를 출력한다.

입력

15

출력

25

 

간단한 규칙을 찾아서 문제를 해결하는 방식인데

0~9는 한 자릿수

10 ~ 99는 두 자릿수

100 ~ 999는 세 자릿수...이다.

 

sum은 자릿수가 변하기 직전의 마지막 숫자이다. 가령 0, 9, 99, 999

index는 sum이 다음 경계의 숫자로 바뀌기 위한 값이다. 가령 9, 90, 900

sum과 index의 합으로 n이 몇 자릿수 숫자인지 검사하게 된다.

 

반복문은 sum과 index의 합이 n보다 작을 때까지 반복한다.

말로 설명하면 복잡하니 예를 들어보자.

[1] N이 200일 때 while( 0 + 9  < 200) while의 조건을 만족한다.

0 + 9 가 가지는 의미가 굉장히 중요한데, N은 적어도 두 자리 숫자는 된다는 의미이다.

따라서 res에 1부터 9까지 자릿수의 합인 9(index) * 1(digit)을 넣어주게 된다.

그다음 반복을 위해 sum을 9로 맞추고 index를 90으로 증가시켜 다음 숫자가 99 이상의 숫자인지 검사한다.

 

[2] while( 9 + 90 < 200) while의 조건을 다시 한번 만족한다.

N은 적어도 세 자릿수 숫자는 된다는 의미이다.

따라서 res에 10부터 99까지 숫자의 총자릿수를 더하게 된다. 90(index) * 2(digit)

 

[3] while( 99 + 900 < 200) while의 조건을 만족하지 못한다.

마지막으로 res에 100부터 200까지 숫자의 총 자릿수를 더하면 된다. ( 200(N) - 99(index) ) * 3(digit) 

#include <iostream>

using namespace std;

int main()
{
	int n, sum = 0, index = 9, digit = 1, res = 0;

	cin >> n;

	while (sum + index < n)
	{
		res += index * digit;
		sum += index;
		index *= 10;
		digit++;
	}
	res += (n - sum) * digit;

	cout << res;
}

마치며

솔직히 쉬운 문제는 아니다 ㅠㅠ..

수학적 사고를 코드로 옮기는 건 정말이지 쉬운 일이 아니다.

10의 거듭제곱을 경계로 숫자의 자릿수가 변하는 건 생각하기 쉬울 수 있어도

index와 sum과 같은 개념을 정의해서 경계를 찾고 자릿수를 구하는 건 또 다른 문제이다.

그렇지만 연습하면 누구나 잘할  수 있듯 언젠가 수학적 사고가 잘 되는 날이 오지 않을까 혼자 곱씹어 본다~~~