์˜ค๋ฅด๋ง‰ ์ˆ˜(11057)

(๋ฌธ์ œ๋งํฌ)

์ด ๋ฌธ์ œ๋Š” ๊ฐ„๋‹จํ•œ ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋ฌธ์ œ์ด๋‹ค.

์ˆ˜์˜ ๊ธธ์ด N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฆ‰ N์ž๋ฆฌ ์˜ค๋ฅด๋ง‰ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ฉด ๋˜๊ธฐ ๋•Œ๋ฌธ์—, d[N]์€ N์ž๋ฆฌ์˜ ์˜ค๋ฅด๋ง‰ ์ˆ˜์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋œ๋‹ค. ์ด๋•Œ d[1]์€ 1010๊ฐœ ์ธ๋ฐ 00~99๊นŒ์ง€๋ฅผ ๋ชจ๋‘ ํ•œ ์ž๋ฆฌ ์˜ค๋ฅด๋ง‰์ˆ˜๋กœ ์นœ๋‹ค.


d[2]๋Š” 5555๊ฐœ ์ธ๋ฐ,

  • ์ฒซ์งธ ์ž๋ฆฌ๊ฐ€ 00์ธ ๊ฒฝ์šฐ๋ฅผ ํฌํ•จํ•˜์—ฌ 00์ผ ๊ฒฝ์šฐ 00~99๊นŒ์ง€ 10๊ฐœ,
  • 11์ผ ๊ฒฝ์šฐ 11~99๊นŒ์ง€ 99๊ฐœ,
  • 22์ผ ๊ฒฝ์šฐ 22~99๊นŒ์ง€ 88๊ฐœ โ€ฆ
  • 99์ผ ๊ฒฝ์šฐ 99๋กœ 11๊ฐœ์ด๋‹ค.

์ด์™€ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ d[1000]๊นŒ์ง€ ํ’€์–ด๋‚ผ ์ˆ˜ ์žˆ๋‹ค.

d[2][0] = 10 // -> d[1][0]+d[1][1]+...d[1][9] ์ด 10๊ฐœ
d[2][1] = 9 // -> d[1][1]+d[1][2]+...d[1][9] ์ด 9๊ฐœ
d[2][2] = 8 // -> d[1][2]+...d[1][9] ์ด 8๊ฐœ

์ตœ์ข…์ฝ”๋“œ

#include <stdio.h>
int d[1001][10];

int main(void)
{
    int sum=0,i,j,k,n;
    scanf("%d",&n);

    for(i=0;i<10;i++){
        d[1][i]=1;
    }

    for(i=2;i<=1000;i++){
        for(j=0;j<10;j++){
            for(k=j;k<10;k++){
                d[i][j]+=d[i-1][k];
                d[i][j]%=10007;
            }
        }
    }
    
    for(i=0;i<10;i++){
        sum+=d[n][i];
        sum %= 10007;
    }

    printf("%d",sum);
    return 0;
}