PS

[๋ฐฑ์ค€] 2225 ํ•ฉ๋ถ„ํ•ด with Python

ํ˜•์ค€_It's 2022. 6. 17. 12:25
728x90
๋ฐ˜์‘ํ˜•

๐Ÿ“Œ BOJ 2225 ํ•ฉ๋ถ„ํ•ด

๐Ÿ’ก ์กฐ๊ฑด

  1. ๋ง์…ˆ์˜ ์ˆœ์„œ๊ฐ€ ๋ฐ”๋€ ๊ฒฝ์šฐ๋Š” ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋กœ ์„ผ๋‹ค(1+2์™€ 2+1์€ ์„œ๋กœ ๋‹ค๋ฅธ ๊ฒฝ์šฐ).
    ๋˜ํ•œ ํ•œ ๊ฐœ์˜ ์ˆ˜๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ์“ธ ์ˆ˜๋„ ์žˆ๋‹ค.
  1. ์ฒซ์งธ ์ค„์— ๋‘ ์ •์ˆ˜ N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  1. ์ฒซ์งธ ์ค„์— ๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.
  1. 0๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ์ •์ˆ˜ K๊ฐœ๋ฅผ ๋”ํ•ด์„œ ๊ทธ ํ•ฉ์ด N์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ
  1. 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

โŒจ๏ธ ๋ฌธ์ œ ํ’€์ด

  1. 0๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ์ •์ˆ˜ K๊ฐœ๋ฅผ ์ด์šฉํ•ด N์„ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์€ 0๋ถ€ํ„ฐ N๊ฐœ๊นŒ์ง€ k-1๋ฅผ ๋งŒ๋“œ๋Š” ๊ฐœ์ˆ˜์˜ ํ•ฉ๊ณผ ๊ฐ™๋‹ค.
  1. (1) ๋ฒˆ์„ ์ ํ™”์‹์œผ๋กœ ํ‘œํ˜„ํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค.
    dp[k][n] = dp[k - 1][n - l] (0 <= l <= n)
  1. (2)์ ํ™”์‹์— ๋”ฐ๋ผ์„œ n = 3, k = 3 ์ผ ๊ฒฝ์šฐ๋Š” ์•„๋ž˜์™€ ๊ฐ™์ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  1. ์ด ์ ํ™”์‹์„ ๊ตฌํ˜„ํ–ˆ์„ ๋•Œ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(n * k) ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
๋ฐ˜์‘ํ˜•