์ค๋ฅด๋ง ์(11057)
์ด ๋ฌธ์ ๋ ๊ฐ๋จํ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ๋ฌธ์ ์ด๋ค.
์์ ๊ธธ์ด N์ด ์ฃผ์ด์ก์ ๋, ์ฆ N์๋ฆฌ ์ค๋ฅด๋ง ์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ฉด ๋๊ธฐ ๋๋ฌธ์, d[N]
์ N์๋ฆฌ์ ์ค๋ฅด๋ง ์์ ๊ฐ์๊ฐ ๋๋ค. ์ด๋ d[1]
์ ๊ฐ ์ธ๋ฐ ~๊น์ง๋ฅผ ๋ชจ๋ ํ ์๋ฆฌ ์ค๋ฅด๋ง์๋ก ์น๋ค.
d[2]
๋ ๊ฐ ์ธ๋ฐ,
- ์ฒซ์งธ ์๋ฆฌ๊ฐ ์ธ ๊ฒฝ์ฐ๋ฅผ ํฌํจํ์ฌ ์ผ ๊ฒฝ์ฐ ~๊น์ง 10๊ฐ,
- ์ผ ๊ฒฝ์ฐ ~๊น์ง ๊ฐ,
- ์ผ ๊ฒฝ์ฐ ~๊น์ง ๊ฐ โฆ
- ์ผ ๊ฒฝ์ฐ ๋ก ๊ฐ์ด๋ค.
์ด์ ๊ฐ์ ๋ฐฉ์์ผ๋ก 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;
}