๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿ‘ทโ€โ™€๏ธ ํƒ€์ผ ์žฅ์‹๋ฌผ ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ


๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

def solution(N):
    rad_array = [1,1]
    for i in range(2,N):
        rad_array.append(rad_array[-1] + rad_array[-2])
    answer = (rad_array[-2] + rad_array[-1]*2)*2
    return answer

DP(Dynamic Programming, ๋™์ ๊ณ„ํš๋ฒ•)์„ ์ด์šฉํ•ด ํ•ด๊ฒฐํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. DP์˜ ๊ณ„ํš์— ๋”ฐ๋ผ ์ „์ฒด ๋ฌธ์ œ๋ฅผ ์ž‘์€ ๋ถ€๋ถ„์œผ๋กœ ๋‚˜๋ˆ„๊ฒ ์Šต๋‹ˆ๋‹ค. ์ตœ์ข…์ ์œผ๋กœ ๊ตฌํ•  ์ง์‚ฌ๊ฐํ˜•์˜ ๋‘˜๋ ˆ๋Š” ๋งˆ์ง€๋ง‰์œผ๋กœ ๊ตฌํ•œ ์ •์‚ฌ๊ฐํ˜•๊ณผ ๊ทธ ์ „ ์ •์‚ฌ๊ฐํ˜•์˜ ๋ณ€์˜ ๊ธธ์ด๋ฅผ ํ†ตํ•ด ๊ตฌํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ณ€์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋กœ ์น˜ํ™˜ํ•ด์„œ ํ’€๊ฒ ์Šต๋‹ˆ๋‹ค.

๊ฐ€์žฅ ์ž‘์€ ์ •์‚ฌ๊ฐํ˜•๋ถ€ํ„ฐ ๊ตฌํ•˜๋ฉด ๋งˆ์ง€๋ง‰์œผ๋กœ ๊ตฌํ•œ ์ •์‚ฌ๊ฐํ˜•์˜ ํ•œ ๋ณ€๊ณผ ๊ทธ ์ „ ์ •์‚ฌ๊ฐํ˜•์˜ ๋ณ€์˜ ๊ธธ์ด ํ•ฉ์ด ๊ตฌํ•˜๊ณ ์žํ•˜๋Š” ๋ณ€์˜ ๊ธธ์ด์ž…๋‹ˆ๋‹ค. ์ด๋Š” rad_array๋ผ๋Š” list ์ž๋ฃŒํ˜•์— ์ €์žฅ๋˜๊ณ , ๋‹ค์Œ ์‹œํ–‰์—์„œ๋„ ์ด๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฉ”๋ชจ์ด์ œ์ด์…˜(memoization) ๊ณผ์ •์„ ํ†ตํ•ด ๋งˆ์ง€๋ง‰ ์ •์‚ฌ๊ฐํ˜•์˜ ๋ณ€์˜ ๊ธฐ๋ฆฌ๊นŒ์ง€ ๊ตฌํ•ฉ๋‹ˆ๋‹ค. ์ตœ์ข…์ ์œผ๋กœ ๊ตฌํ˜„ ์ •์‚ฌ๊ฐํ˜•๋“ค์˜ ๋ณ€์˜ ๊ธธ์ด๋ฅผ ํ†ตํ•ด ๊ตฌํ•˜๊ณ ์žํ•˜๋Š” ๋‘˜๋ ˆ๋ฅผ ๊ตฌํ•˜๋ฉด ๋ฌธ์ œ๋Š” ํ•ด๊ฒฐ๋ฉ๋‹ˆ๋‹ค.

Written with StackEdit.


๋ฐ˜์‘ํ˜•