๋ฌธ์
https://www.acmicpc.net/problem/11726
๋ฐฑ์ค ๋ฌธ์ ์ง - BOJ ๊ธธ๋ผ์ก์ด ๋ฒ ํ (1)
ํ์ด
2×n ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ 1×2, 2×1 ํ์ผ๋ก ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
DP(๋์ ํ๋ก๊ทธ๋๋ฐ)๋ก ๋ถ๋ฅ๋์ด์์ผ๋ ์ ํ์์ ์ฌ์ฉํ๋๊ฑด ๋น์ฐํ๊ณ , ๋๊ฐ ์ฒดํฌํด๋ณธ๊ฒฐ๊ณผ ํผ๋ณด๋์น์ผ๊ฑฐ๋ ์๊ฐ์ด ๋ค์๋ค.
์ผ๋จ n = 1, 2, 3...์ผ๋๋ฅผ ๊ฐ์ ํ๋ฉฐ ๊ณ์ฐํด๋ณด๋ ์ญ์ ํผ๋ณด๋์น ์์ด๊ณผ ๋น์ทํ ๊ฒฐ๊ณผ๊ฐ ๋์๋ค.
n = 1์ผ๋ ๐ 1
n = 2์ผ๋ ๐ 2
n = 3์ผ๋ ๐ 3
n = 4์ผ๋ ๐ 5
...
๊ธฐ์กด์ ํผ๋ณด๋์น ์์ด์ f(0) = 0, f(1) = 1๋ฅผ ๋ฒ ์ด์ค๋ก f(2) = 1, f(3) = 2...์ด๋ฏ๋ก ํ์นธ์ฉ ๋ก๊ฒจ์ฃผ๊ธฐ๋ง ํ๋ฉด ๋๋ค.
์ฆ f(1) = 1, f(2) = 2...๋ก ์งํ๋๋ ์
์ด๋ค.
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 31120KB / ์๊ฐ: 44ms
from sys import stdin
n = int(stdin.readline())
mod = 10007
def fibonacci(n):
arr = [0] * (n+1)
arr[1] = 1
if n >= 2:
arr[2] = 2
for i in range(3, n+1):
arr[i] = (arr[i-1] + arr[i-2]) % mod
return arr[n]
print(fibonacci(n))
ํ๋ฐ ๋ค๋ฅธ ํ์ด๋ค์ ๋ณด๋ ์กฐํฉ์ ์ด์ฉํ๋ ๋ฐฉ๋ฒ๋ ์์๋ค.n๊ฐ์ ํ์ผ๋ง์ ํ ๋, 2 x 1 ํ์ผ์ i๊ฐ ์ฌ์ฉํ๊ณ ๋๋จธ์ง๋ฅผ 1 x 2 ํ์ผ๋ก ์ฑ์ฐ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ณ์ฐํ๋ ๋ฐฉ์์ด๋ค.
2 x 1 ํ์ผ์ i๊ฐ ์ฌ์ฉํ๋ฉด ๋จ์ ๊ณต๊ฐ์ n - i * 2๊ฐ ๋๋๋ฐ, ์ด ๊ณต๊ฐ์ ๋ชจ๋ 1 x 2 ํ์ผ๋ก ์ฑ์ฐ๋๊ฒ์ด๋ค.
์กฐํฉ ๊ณต์์ ์ฌ์ฉํด์ $ _nC_r = \frac{n!}{r!(n-r)!} $ ๊ณผ ๊ฐ์ด ๊ณ์ฐํ๋ฉด ๋๋ค.
# ๋ฉ๋ชจ๋ฆฌ: 33372KB / ์๊ฐ: 68ms
from sys import stdin
from math import factorial
n = int(stdin.readline())
mod = 10007
ret = 0
for i in range(n//2 + 1):
ret += factorial(n-i) // factorial(i) // factorial(n - i*2)
print(ret % mod)
ํผ๋ณด๋์น๋ฅผ ์ฌ์ฉํ๋ํธ์ด ๋ ํจ์จ์ ์ด๋ค.