์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ/BOJ_Python

[BOJ/Step15] 1003 : ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ (Python)

NaNaRin๐Ÿ™ƒ 2021. 2. 22. 21:41

www.acmicpc.net/problem/1003

 

1003๋ฒˆ: ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์™€ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•œ๋‹ค.

www.acmicpc.net


ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋ž‘ ๋˜‘๊ฐ™๋‹ค

0์ด ์ž…๋ ฅ๋˜๋ฉด 0์ด ํ•œ๋ฒˆ ์ถœ๋ ฅ๋˜๊ณ  0๋ฒˆ์งธ fibonacci ์ˆ˜๋Š” 1์ด๋‹ค

1์ด ์ž…๋ ฅ๋˜๋ฉด 1์ด ํ•œ๋ฒˆ ์ถœ๋ ฅ๋˜๊ณ  1๋ฒˆ์งธ fibonacci ์ˆ˜๋Š” 1์ด๋‹ค

2๊ฐ€ ์ž…๋ ฅ๋˜๋ฉด 0๊ณผ 1์ด ํ•œ๋ฒˆ์”ฉ ์ถœ๋ ฅ๋˜๊ณ  2๋ฒˆ์งธ fibonacci ์ˆ˜๋Š” 2์ด๋‹ค

โ€ฆ

 

์ญ‰ ๋‚˜์—ดํ•˜๋‹ค ๋ณด๋ฉด ๊ทœ์น™์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

 

ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์™€ ๊ฐ™์ด n๋ฒˆ์งธ 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋Š” 

n-1๋ฒˆ์งธ 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜ + n-2๋ฒˆ์งธ 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์ด๊ณ 

n๋ฒˆ์งธ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋Š”

n-1๋ฒˆ์งธ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜ + n-2๋ฒˆ์งธ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์ด๋‹ค

 

๊ทœ์น™์„ ์•Œ์•˜์œผ๋‹ˆ ์ž…๋ ฅ๋˜๋Š” n์˜ ์ตœ๋Œ“๊ฐ’ 40๊นŒ์ง€ ๋ฏธ๋ฆฌ ๋ฆฌ์ŠคํŠธ์— 0๊ณผ 1 ํšŸ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜์—ฌ ์ €์žฅํ•ด ๋‘”๋‹ค

 

python
๋‹ซ๊ธฐ
# 1003.py n = int(input()) fibo0 = [1, 0] fibo1 = [0, 1] for i in range(39): โ€‹โ€‹โ€‹โ€‹fibo0.append(fibo0[i] + fibo0[i+1]) โ€‹โ€‹โ€‹โ€‹fibo1.append(fibo1[i] + fibo1[i + 1]) for _ in range(n): โ€‹โ€‹โ€‹โ€‹num = int(input()) โ€‹โ€‹โ€‹โ€‹print(fibo0[num], fibo1[num])