[C++] 3의 개수 (large) 🔥

📄문제

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개있는지 구하려고 합니다.
예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다.
자연수 N이 입력되면 1부터 N까지 숫자를 적을 때, 3의 개수가 몇 개인지 구하여 출력하는 프로그램을 작성하세요.

 

⬇️ 입력

첫 줄에 자연수의 개수 N(3<=N<=1,000,000,000)이 주어집니다.

15

 

⬆️ 출력

3의 개수를 출력하세요.

2

 

📝 풀이

#include <iostream>
#include <string>

using namespace std;
int main()
{
	int N;
	int cnt = 0;
	scanf_s("%d", &N);

	// 입력값을 문자열로
	string str = to_string(N);

	// 문자열의 개수만큼 반복
	for (int i = str.length() - 1; i >= 0; --i)
	{
		int digit = pow(10, str.length() - 1 - i); // 현재 center에 해당하는 자리수

		int left = (i == 0) ? 0 : N / digit / 10; // center 기준 왼쪽
		int center = str[i] - '0'; // 현재 선택한 자리수에 해당하는 값
		int right = (i == str.length() - 1) ? 0 : N % digit; // center 기준 오른쪽 값

		if (center > 3) // center가 3보다 크다면?
		{
			cnt += (left + 1) * digit; // 3을 출력하는 개수는 left 개수 + 1 (자신을 포함)
		}
		else if (center < 3) // center가 3보다 작다면?
		{
			cnt += left * digit; // 3을 출력하는 개수는 left 개수 (자신을 제외)
		}
		else // center가 3이라면?
		{
			cnt += left * digit + right + 1; // 자신을 모두 포함하지 않고, right 개수 + 1만큼 포함
		}
	}

	printf("%d", cnt);
}

• N의 범위가 매우 크기때문에, 이것을 for문으로 단순히 검사하는것은 불가능합니다.
• 입력한 숫자의 각 자리수에서 왼쪽, 오른쪽의 개수를 구한 후 공식에 맞게 대입하여 계산합니다.