Boj 1019) 책 페이지

문제

백준 1019

설명

코드 주석으로도 충분히 설명이 된다.

시간 복잡도

O(\(\log{N}\))

코드

#include <bits/stdc++.h>

using ll = long long;
int ans[10];

int main()
{
	fastio;
	ll n;
	cin >> n;

	// 1의 자리에서 가능한 (0~9) 의 갯수, 10의 자리에서 ... 이렇게 계산함.
	// n = 356 일 때 두번째 자리 기준으로 주석을 달았음
	for (ll i = 1; i <= n; i *= 10)
	{
		ll next = i * 10;
	    ll cur_digit  = (n % next) / i;   // 현재 자리수
		ll next_digit = n / next;         // 다음 자리수
		
		// 다음 자리수에 의해(0x0 ~ 2x9) 추가되는 수
		if (next_digit > 0)
		{
			for (int j = 1; j < 10; j++) 
				ans[j] += next_digit * i;
		    ans[0] += (next_digit - 1) * i;
		}
	
		// 현재 자리수에서 이하 자리수를 고려할 필요 없는 경우 (300 ~ 349)
		for (int j = 1; j < cur_digit; j++) 
			ans[j] += i;
		if(next_digit > 0 && cur_digit != 0)
			ans[0] += i;
	
		// 현재 자리수에서 이하 자리수 만큼 추가 (350 ~ 356).
		ans[cur_digit] += n % i + 1;  
	}
	for (int i = 0; i < 10; i++)
		cout << ans[i] << ' ';
}