๐ฏ CodingTest/BaekJoon
[BaekJoon] 1003 ํผ๋ณด๋์น ํจ์
S.Honey
2022. 4. 12. 09:26
โถ ๋ฌธ์
import sys
n = int(sys.stdin.readline().rstrip())
data = {i : 0 for i in range(41)}
# ์ซ์์ ์ต๋๊ฐ์ด 40
result = [[0, 0] for i in range(41)]
result[0][0] = 1
result[1][1] = 1
def fibo(n):
if n == 0:
return 0
elif n == 1:
return 1
elif data[n] > 0:
return data[n]
else:
data[n] = fibo(n-1) + fibo(n-2)
result[n][0], result[n][1] = result[n-1][0] + result[n-2][0], result[n-1][1] + result[n-2][1]
return data[n]
for i in range(n):
num = int(sys.stdin.readline().rstrip())
fibo(num)
sys.stdout.write(str(result[num][0]) +' '+ str(result[num][1]) +'\n')
โถ ๋ฌธ์ ํ์ด
1. ์ ํ์๊ฐ์ด ์งง์ ํธ => DP or ์ด๋ถํ์
2. ์ฌ๊ธฐ์๋ DP๊ฐ ์ ์ ํ๋ค๊ณ ํ๋จ
3. DP๋ก ์ฌ์ฉํ Dictionary์ List๋ฅผ ์ ์ธ
- Dictionary => ํผ๋ณด๋์น ์๋ฅผ ์ ์ฅ
- List => 0๊ณผ 1์ด ๋ฑ์ฅํ ํ์ ์ ์ฅ
- List์ ์ด๊ธฐ๊ฐ ์ค์ => 0์ธ๊ฒฝ์ฐ 1์ธ๊ฒฝ์ฐ
4. fibo ์ฌ๊ท ํจ์๋ฅผ ํตํด ๊ฒฐ๊ณผ๋ ํผ๋ณด๋์น์๋ฅผ ๋ฆฌํดํ๋ฉด์ result๋ฆฌ์คํธ์ ์ด์ ๊ฐ๋ค์์ ๋ฑ์ฅํ 0๊ณผ 1์ ๋ฑ์ฅํ์๋ฅผ ๋์ + ํน ์ด๋ฏธ ์ฐ์ฐ๋ ํผ๋ณด๋์น ์๋ผ๋ฉด ์ ์ฅ๋ ๊ฐ์ ๋ฐํ
5. ๊ฐ๊ฐ์ ๊ฒฝ์ฐ๋ง๋ค ์ถ๋ ฅ