Boj 14912) 숫자 빈도수

문제

백준 14912

설명

그냥 O(n) 의 브루트포스로도 풀리는 문제지만 분석적으로 더 풀어보았음.

범위의 끝을 a, 원하는 수를 b 라고 하면

• 10의 자리마다 b로 고정시켜놓고 그 갯수를 계산하는 것임.
• 5번째 자리를 고정하면 XXXX b XXXX 이런 모양으로 만드는 것임.

편의상 함수를 정의함

• i 번째 수를 고정할 때 앞에부분을 front(a, i) 라고 하겠음.
  • front(123, 1) == 12 임
• i 번째 수를 Th(a, i) 라고 하겠음.
  • Th(123, 2) == 2 임.

이때 2가지 케이스로 나누는데

• 앞에부분이 0 ~ front(a, i)-1 인 경우
  • b == 0 이면 1 ~ front(a, i)-1
• 앞에부분이 front(a, i) 인 경우

전자의 케이스는 뒷자리가 a 와 관계가 없음

• front(a, i) * 10^(i-1) 만큼 있는 것임.
  • b == 0 이면 clamp(front(a, i)-1, 0, max) * 10^(i-1)
• a = 1234, b = 4, i = 2 이라고 하면
  • 004(0~9), 014(0~9) … 114(0~9) 이렇게 있어 12 * 10 개가 만들어짐.

후자의 케이스는 Th(a, i) 보다 b 가 큰지의 여부에 따라 결정됨.

• b 보다 작으면 더할 수가 없음.
  • a = 123, b = 4, i = 2 이라고 하면
    • 14x 이런 수는 값을 초과하기 때문임.
• b 보다 크면 그냥 10^(i-1) 을 더해주면 됨
  • a = 1234, b = 1, i = 3 이라고 하면
    • 11xx 이런 수는 뒤에 0~99 을 그대로 쓸 수 있기 때문임.
• b 와 같으면 a % (10&(i-1)) + 1` 만큼의 수가 가능하게 됨
  • a = 123, b = 2, i = 2 이라고 하면
    • 12x 는 뒤에 0, 1, 2, 3 만 가능하기 때문임.
• 단 b==0 이고 i 가 마지막 자리수이면 계산 안함
  • 처음 수가 0 으로 시작하지 못하기 때문임

시간 복잡도

O(자리수)

코드

int NthNum(int x, int th)
{
	int t = 1;
	while (th-- > 1) t *= 10;
	return (x / t) % 10;
}

int main()
{
	int a, b, ans = 0;

	cin >> a >> b;

	for (int i = 1, cnt = 1; a / i != 0; i *= 10, cnt++)
	{
		if (b != 0) {
			ans += a / (i * 10) * i;  // 0bxx ~ x(x-1)bxx
			int th = NthNum(a, cnt);
			if (th > b) ans += i;
			else if (th == b) ans += a % i + 1;
		}
		else {
			ans += clamp(a / (i * 10) - 1, 0, numeric_limits<int>::max()) * i;
			int th = NthNum(a, cnt);
			if (a / (i * 10) > 0)
			{
				if (th > b) ans += i;
				else if (th == b) ans += a % i + 1;
			}
		}
	}

	cout << ans;
}