3의 개수는?(small)


자연수 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<=100,000)이 주어집니다.

▣ 출력설명
3의 개수를 출력하세요.

▣ 입력예제 1 
15

▣ 출력예제 1
2


풀이

각각의 숫자에서 3의 개수를 구하는 함수를 만들고 n까지 모두 돌면서 3의 개수를 세어주었다.
이 방법은 숫자가 작을 때는 가능하지만 N2의 사간을 가지고 있어서 좋지 못하다.

int countIn3(int num)
{
	int ret = 0;

	while (num > 0)
	{
		if (num % 10 == 3)
			ret++;

		num /= 10;
	}

	return ret;
}

void solve()
{
	long long n;
	cin >> n;

	int sum = 0;
	for (long long i = 1; i <= n; ++i)
		sum += countIn3(i);

	cout << sum;
}

전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>

using namespace std;

int countIn3(int num)
{
	int ret = 0;

	while (num > 0)
	{
		if (num % 10 == 3)
			ret++;

		num /= 10;
	}

	return ret;
}

void solve()
{
	long long n;
	cin >> n;

	int sum = 0;
	for (long long i = 1; i <= n; ++i)
		sum += countIn3(i);

	cout << sum;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고