๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/11057
์ฝ๋ ์ ์ถ ๊ธฐ๋ก (๋ฉ๋ชจ๋ฆฌ ๋ฐ ์๊ฐ)
๋ฉ๋ชจ๋ฆฌ : 123172 KB
์๊ฐ : 120 ms
Code
N = int(input())
dp = [[0 for _ in range(19)] for _ in range(1009)]
dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, N+1):
for j in range(10):
if j == 0:
dp[i][j] = sum(dp[i-1])
else:
dp[i][j] = dp[i][j-1] - dp[i-1][j-1]
print(sum(dp[N])%10007)
Python
๋ณต์ฌ
๋ฉ๋ชจ
DP[][] ๋ฐฐ์ด์ 2์ฐจ์์ผ๋ก ์ ์ธ
DP[x][y] โ x : ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ์ซ์ ( = ์ค๋ฅด๋ง์์ ๊ธธ์ด )
y : ๊ฐ์ฅ ํฐ ์๋ฆฌ์ ์ซ์
< ์์ >
000 โ dp[3][0]
3367 โ dp[4][3]
Python
๋ณต์ฌ
dp[1] ๋ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ์ผ๋ก ์ด๊ธฐํ
์์ ๊ทธ๋ฆผ์ ์ํด, dp[k][0] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]
dp[k][1] = dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]
dp[k][2] = dp[k-1][2] + ... + dp[k-1][9]
.
.
.
dp[k][9] = ... dp[k-1][9]
๋ผ๋ ๊ท์น์ ์ฐพ์ ์ ์์ผ๋ฏ๋ก
j == 0์ผ๋๋
dp[i][j] = sum(dp[i-1])
j โ 0 ์ผ๋๋
dp[i][j] = dp[i][j-1] - dp[i-1][j-1]
์ ๊ท์น์ ์ป์ ์ ์๋ค
์ฐธ์กฐ
< ํ์ด์ฌ ๋ฐฐ์ด์ ๊ฐ ์ ๋ถ ๋ํ๊ธฐ >
arr = [1, 2, 3, 4, 5]
sum(arr)
Python
๋ณต์ฌ