์ค๋ฅด๋ง ์๋ ์์ ์๋ฆฌ๊ฐ ์ค๋ฆ์ฐจ์์ ์ด๋ฃจ๋ ์๋ฅผ ๋งํ๋ค. ์ด๋, ์ธ์ ํ ์๊ฐ ๊ฐ์๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์น๋ค.
์๋ฅผ ๋ค์ด, 2234์ 3678, 11119๋ ์ค๋ฅด๋ง ์์ด์ง๋ง, 2232, 3676, 91111์ ์ค๋ฅด๋ง ์๊ฐ ์๋๋ค.
์์ ๊ธธ์ด N์ด ์ฃผ์ด์ก์ ๋, ์ค๋ฅด๋ง ์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ 0์ผ๋ก ์์ํ ์ ์๋ค.
๋์ด 0์ผ๋ก ๋๋๋ฉด ๋ค์ 0~9๊น์ง 10๊ฐ์ ์ซ์๊ฐ ์ฌ ์ ์๋ค. ๊ธธ์ด๊ฐ 10์ธ 1์ฐจ์ ๋ฐฐ์ด์ ๊ฐ ์ธ๋ฑ์ค๊ฐ ๋๋๋ ์ซ์๋ผ๊ณ ํ ๋, ์ธ๋ฑ์ค 0์ ์๋ ๊ฐ๋ค์ 1~9๊น์ง์ ์ธ๋ฑ์ค ๊ฐ์ ๋ชจ๋ ๋ํด์ ธ์ผ ํ๋ค.
2์ฐจ์์ผ๋ก ํ ์๋ ์๊ณ , 1์ฐจ์์ผ๋ก ๋์ ํด์ ํ ์ ์๋ ๋ ๊ฐ์ง ๋ฐฉ๋ฒ ์กด์ฌ
๊ฐ 10๊ฐ์ ์ด์ ๊ฐ๋ n๊ฐ ํ์ 2์ฐจ์ ๋ฐฐ์ด
# ์ค๋ฅด๋ง ์
n = int(input())
dp = [[None] for _ in range(n)]
dp[0] = [1]*10
for i in range(1, n):
dp[i] = [sum(dp[i-1][x:]) for x in range(10)]
print(sum(dp[-1])%10007)
๊ฐ๋ค์ ๋์ ํด์ ๋ํด๋๊ฐ๋ 1์ฐจ์ ๋ฐฐ์ด
n = int(input())
dp =[1] * 10
for i in range(1,n+1):
for j in range(1,10):
dp[j] += dp[j-1]
print(dp[9]%10007)