BOJ1019 책 페이지

www.acmicpc.net/problem/1019

1019번: 책 페이지

 

이런 거 초등학생 때 많이 풀었던 것 같은데,, 경우의 수같은 거 배울 때 나오는 문제임

 

처음엔 2459가 있을 때

0001~2000

2001~2400

2401~2450

2451~2459

이렇게였나 뭐 비슷하게 수의 범위로 나눠서 생각하는 걸 시도했음. (실패함)

 

 

자릿수로 나눠서 생각하는 게 더 편했다.

1이 등장하는 횟수는

일의 자리가 1인 수의 개수 + 십의 자리가 1인 수의 개수 + ... 이거니까

 

N=2458,

 

(1) 일의 자리가 k인 수의 개수

 = _ _ _ k 인 수의 개수

 = if ( 0≤k≤8 ), [ _ _ _ = 000 ~ 245 ]

    if ( k>8 ), [ _ _ _ = 000 ~ 244 ]

    if ( k=0 ), [ _ _ _ = 000 ] 빼기

 

(2) 십의 자리가 k인 수의 개수

 = _ _ k _ 인 수의 개수

 = if( 0≤k<5 ), [ _ _ = 00 ~ 24 ]×[ _ = 0 ~ 9 ]

    if( k=5 ), [ _ _ = 00 ~ 23 ]×[ _ = 0~9 ]+[ _ _ = 24 ]×[ _ = 0~8 ]

    if( k>5 ), [ _ _ = 00 ~ 23 ]×[ _ = 0~9 ]

    if( k= 0), [ _ _ = 00 ]×[ _ = 0~9 ] 빼기

 

(3) 백의 자리가 k인 수의 개수 ((2)와 방식이 같음)

= _ k _ _ 인 수의 개수

= if( 0≤k<4 ), [ _ = 0 ~ 2 ]×[ _ _ = 00 ~ 99 ]

   if( k=4 ), [ _ = 0 ~ 1 ]×[ _ _ = 00 ~ 99 ]+[ _ = 2 ]×[ _ _ = 00 ~ 58 ]

   if( k>4 ), [ _ = 0 ~ 1 ]×[ _ _ = 00 ~ 99 ]

   if( k=0 ), [ _ = 0 ]×[ _ _ = 00~99 ] 빼기

 

(4) 천의 자리가 k인 수의 개수

= k _ _ _ 인 수의 개수

= if( 0<k<2 ), [ _ _ _ = 000~999 ]

= if( k=2 ), [ _ _ _ = 000~458 ]

 

각각 구해서 배열에 저장해줌.

 

(2), (3)은 동작 방식이 같으니 for문으로 돌려준다.

 

너무 헷갈려,,,

 

 

 

코드

// book page
#include <cstdio>
using namespace std;

int main() {
	int N, digit = 0;
	int d[11] = { 0, }, a[11] = { 0, }, b[11] = { 0, };
	int cnt[10] = { 0, }, ten[11];
	
	ten[0] = 1;
	scanf("%d", &N);
	if (N < 10) {
		printf("0 ");
		for (int i = 1; i <= N; ++i) printf("1 ");
		for (int i = N + 1; i < 10; ++i) printf("0 ");
		return 0;
	}

	while (N) {
		d[digit] = N % 10; N /= 10;
		a[digit] = N;
		ten[digit + 1] = ten[digit] * 10; digit++;
	}
	digit--;
	for (int i = 0; i < digit; ++i) b[i + 1] = b[i] + d[i] * ten[i];

	int num = 0;
	for (; num <= d[0]; ++num) cnt[num] += a[0] + 1;
	for (; num < 10; ++num) cnt[num] += a[0];
	cnt[0]--;

	for (int i = 1; i < digit; ++i) {
		int inc1 = ten[i] * (a[i] + 1);
		int inc2 = inc1 - ten[i];
		num = 0;

		for (; num < d[i]; ++num) cnt[num] += inc1;
		for (; num < 10; ++num) cnt[num] += inc2;
		cnt[0] -= ten[i];
		cnt[d[i]] += (b[i] + 1);
	}
	
	for (num = 1; num < d[digit]; ++num) cnt[num] += ten[digit];
	cnt[d[digit]] += b[digit] + 1;

	for (int num = 0; num < 10; ++num) printf("%d ", cnt[num]);
	return 0;
}