๐Ÿ’ฏ CodingTest/BaekJoon

[BaekJoon] 1003 ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜

S.Honey 2022. 4. 12. 09:26

โ–ถ ๋ฌธ์ œ

[์ถœ์ฒ˜ : https://www.acmicpc.net/problem/1003]

 

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. ๊ฐ๊ฐ์˜ ๊ฒฝ์šฐ๋งˆ๋‹ค ์ถœ๋ ฅ