Search
Duplicate
๐Ÿฅˆ

์˜ค๋ฅด๋ง‰ ์ˆ˜

์ฃผ์ฐจ
15
๋ฌธ์ œ๋ฒˆํ˜ธ
10057
์–ธ์–ด
Python
ํ‹ฐ์–ด
์‹ค๋ฒ„
์œ ํ˜•
DP
nj_Blog
O
nj_์ƒํƒœ
์™„๋ฃŒ
์ดํ•ด๋„
ํ’€์ด
์‚ฌ๋žŒ
์ดํ•ด๋„ 2
13 more properties

๋ฌธ์ œ๋งํฌ

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
๋ณต์‚ฌ