[210203] 11번 숫자의 총 개수(small), 12번 숫자의 총 개수(large)

KeonWoo Kim·2021년 2월 3일

목록 보기

4/84

11번 문제

자연수 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)이 주어진다.
▣ 출력설명
첫 번째 줄에 숫자의 총개수를 출력한다.

입출력

▣ 입력예제 1
15
▣ 출력예제 1
21

풀이

입력받은 n까지 첫번째 반복문을 돌면서 각 값이 0이 되기전까지의 두번째 반복문 안에서 각 값을 10으로 나눈 값을 합계에 더하는 방식으로 문제를 해결할 수 있다.

코드

#include <iostream>
using namespace std;

int main()
{
	int n, tmp, sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		tmp = i;
		while (tmp != 0)
		{
			tmp = tmp / 10;
			sum++;
		}
	}
	printf("%d\n", sum);

}

12번 문제

▣ 입력설명
첫 번째 줄에는 자연수 N(3<=N<=100,000,000)이 주어진다.
▣ 출력설명
첫 번째 줄에 숫자의 총개수를 출력한다.

입출력

▣ 입력예제 1
15
▣ 출력예제 1
21

풀이

11번을 해결한 방식은 시간복잡도가 O(n^2)로 제한시간 1초를 초과하게 된다.
따라서 다른 방법으로 접근해야 한다.

1자리 숫자는 1부터 9까지 총 9개가 있다
2자리 숫자는 10부터 99까지 총 90개가 있다
3자리 숫자는 100부터 999까지 총 900개가 있다.
4자리 숫자는 1000부터 9999까지 총 9000개가 있다.
...

예를 들어 입력받은 값이 256라면 1자리 숫자 19개 + 2자리 숫자 290개 + 3자리수 3*(256-99)개 = 660개가 된다.
이러한 방법을 통해 문제를 해결해나가면 된다.

res는 결과값을 의미한다. 0으로 초기화한다.
sum에는 누적되는 값을 저장한다. 0으로 초기화한다.
cnt는 자릿수를 의미한다. 1로 초기화한다.
de는 각 자릿수에 포함된 숫자의 갯수를 나타내기 위한 공식을 위한 값이다. 9로 초기화한다.
즉 cnt와 de를 곱하면 각 자릿수에 포함된 총 숫자의 갯수를 알 수 있다.

예를들어
자릿수가 1이면 cnt=1, de=9이므로 총 9개의 숫자가 존재한다
자릿수가 2이면 cnt=2, de=90이므로 총 180개의 숫자가 존재한다.
자릿수가 3이면 cnt=3, de=900이므로 총 2700개의 숫자가 존재한다.

반복문을 탈출하기 위한 조건은 sum과 de의 합이 입력값보다 작을때로 한다.
위 조건을 통해 입력받은 숫자에 모두 포함되어 있는 자릿수에 있는 숫자들의 합을 알 수 있다.
ex) 입력받은 값이 256이면 자릿수가 1과 2인 숫자들의 총 합인 189이 나오게 된다.

반복문을 탈출하게 되고나서 100부터 256까지의 숫자 갯수를 알기 위해서는
입력받은값 256에 자릿수 1과 2인 숫자의 합을 빼고 곱하기 3을 하면된다.

res = res + (n-sum) * cnt;

코드

#include <iostream>
using namespace std;

int main()
{
	int n, sum = 0, cnt = 1, de = 9, res = 0;

	cin >> n;

	while (sum + de < n) 
	{
		res = res + (cnt * de); 
		sum = sum + de; // 반복문을 탈출하기 위한 조건
		cnt++; // 자릿수 증가
		de = de * 10; // 9->90->900->...
	}
	res = res + (n - sum) * cnt;

	printf("%d", res);
}