-
[๋ฐฑ์ค] 2225 ํฉ๋ถํด with PythonPS 2022. 6. 17. 12:25728x90๋ฐ์ํ
๐ BOJ 2225 ํฉ๋ถํด
๐ก ์กฐ๊ฑด
- ๋ง์
์ ์์๊ฐ ๋ฐ๋ ๊ฒฝ์ฐ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ๋ก ์ผ๋ค(1+2์ 2+1์ ์๋ก ๋ค๋ฅธ ๊ฒฝ์ฐ).
๋ํ ํ ๊ฐ์ ์๋ฅผ ์ฌ๋ฌ ๋ฒ ์ธ ์๋ ์๋ค.
- ์ฒซ์งธ ์ค์ ๋ ์ ์ N(1 โค N โค 200), K(1 โค K โค 200)๊ฐ ์ฃผ์ด์ง๋ค.
- ์ฒซ์งธ ์ค์ ๋ต์ 1,000,000,000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค.
- 0๋ถํฐ N๊น์ง์ ์ ์ K๊ฐ๋ฅผ ๋ํด์ ๊ทธ ํฉ์ด N์ด ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
- DP, ๋ค์ด๋๋ฏนํ๋ก๊ทธ๋๋ฐ ์ ํ์ ๋ฌธ์
๐ฅ ์์ค ์ฝ๋
n, k = map(int, input().split()) mod = 1000000000 dp = [[0] * (n + 1) for _ in range(k + 1)] dp[0][0] = 1 for i in range(1, k + 1): for j in range(n + 1): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] dp[i][j] %= mod print(dp[k][n])
๐ ์์ ๋ฐ ์คํ๊ฒฐ๊ณผ
์์
20 2
์คํ๊ฒฐ๊ณผ
21
โจ๏ธ ๋ฌธ์ ํ์ด
- 0๋ถํฐ N๊น์ง์ ์ ์ K๊ฐ๋ฅผ ์ด์ฉํด N์ ๋ง๋๋ ๋ฐฉ๋ฒ์ 0๋ถํฐ N๊ฐ๊น์ง k-1๋ฅผ ๋ง๋๋ ๊ฐ์์ ํฉ๊ณผ ๊ฐ๋ค.
- (1) ๋ฒ์ ์ ํ์์ผ๋ก ํํํ๋ฉด ์๋์ ๊ฐ๋ค.
dp[k][n] = dp[k - 1][n - l] (0 <= l <= n)
- (2)์ ํ์์ ๋ฐ๋ผ์ n = 3, k = 3 ์ผ ๊ฒฝ์ฐ๋ ์๋์ ๊ฐ์ด ํํํ ์ ์์ต๋๋ค.
- ์ด ์ ํ์์ ๊ตฌํํ์ ๋ ์๊ฐ๋ณต์ก๋๋ O(n * k) ๋ก ํํํ ์ ์์ต๋๋ค.
๋ฐ์ํ'PS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 9996 ํ๊ตญ์ด ๊ทธ๋ฆฌ์ธ ๋ ์๋ฒ์ ์ ์ํ์ง with Python (0) 2022.06.29 [๋ฐฑ์ค] 6236 ์ฉ๋ ๊ด๋ฆฌ with Python (0) 2022.06.17 [๋ฐฑ์ค] 1915 ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ with Python (0) 2022.06.17 [๋ฐฑ์ค] 1700 ๋ฉํฐํญ ์ค์ผ์ค๋ง with Python (0) 2022.06.16 [๋ฐฑ์ค] 1525 ํผ์ฆ with Python (0) 2022.06.14 - ๋ง์
์ ์์๊ฐ ๋ฐ๋ ๊ฒฝ์ฐ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ๋ก ์ผ๋ค(1+2์ 2+1์ ์๋ก ๋ค๋ฅธ ๊ฒฝ์ฐ).