1019 책 페이지

1019 책 페이지 해법

---

백준 온라인 저지 사이트에 올라와있는 문제이다.

문제 링크

특수한 알고리즘이 필요한 문제는 아니고 수학적인 통찰력으로 해결할 수 있는 문제이다. 입력받은 수의 각 자릿수들을 a₁a₂…a_i…a_n-1a_n라고 할때 i번째 자리에 특정 숫자가 몇번씩 등장하는지 고민해보면 문제를 해결할 수 있다.

숫자 target이 i번째 자리에 몇번 등장하는지 구하는 방법은 아래와 같다.

1) a_i == target 인 경우

• a₁a₂…a_i-1 * 10^n-i + a_i+1a_i+2…a_n + 1

2) a_i > target 인 경우

• a₁a₂…a_i-1 * 10^n-i

3) a_i < target 인 경우

• (a₁a₂…a_i-1 + 1) * 10^n-i

이때 target == 0 인 경우에는 위와는 조금 다르게 구해야 한다. 자세한 내용은 코드 참고.

#include<cstdio>

using namespace std;

int main()
{
	long long n,arr[10]={0,};
	scanf("%lld",&n);
	for(int i=0;i<10;i++)
	{
		long long bias = 1;
		while(bias<=n)
		{
			long long l = n/bias/10;
			long long target = (n/bias)%10;
			long long r = n%bias;
			if(i==0)
			{
				if(target == i && bias != 1)
				{
					arr[i] += (l-1) * bias + r + 1;
				}
				else{
					arr[i] += l*bias;
				}
			}
			else{
				if(target == i)
				{
					arr[i] += l * bias + r + 1;
				}
				else if(target < i)
				{
					arr[i] += l * bias;
				}
				else{
					arr[i] += (l+1) * bias;
				}
			}
			bias *= 10; 
			//printf("%d\n",arr[i]);
		}
		printf("%lld ",arr[i]);
	}
}