[BOJ-2748] 피보나치 수 2

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 F_n = F_n-1 + F_n-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

제한

 

예제 입력 1

10

예제 출력 1

55

힌트

 

W3sicHJvYmxlbV9pZCI6IjI3NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4IDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWIyOTQgMFx1YWNmYyAxXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gMFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViMjk0IDBcdWM3NzRcdWFjZTAsIDFcdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YjI5NCAxXHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIDJcdWJjODhcdWM5ZjggXHViZDgwXHVkMTMwXHViMjk0IFx1YmMxNFx1Yjg1YyBcdWM1NWUgXHViNDUwIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViOTdjIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWMzNjhcdWJjZjRcdWJhNzQgRjxzdWI+bjxcL3N1Yj4gPSBGPHN1Yj5uLTE8XC9zdWI+ICsgRjxzdWI+bi0yPFwvc3ViPiAobiZndDs9MilcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5uPTE3XHVjNzdjXHViNTRjIFx1YWU0Y1x1YzljMCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViOTdjIFx1YzM2OFx1YmNmNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD4wLCAxLCAxLCAyLCAzLCA1LCA4LCAxMywgMjEsIDM0LCA1NSwgODksIDE0NCwgMjMzLCAzNzcsIDYxMCwgOTg3LCAxNTk3PFwvcD5cclxuXHJcbjxwPm5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gblx1Yzc0MCA5MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpYm9uYWNjaSBOdW1iZXIgMiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIEZpYm9uYWNjaSBzZXF1ZW5jZSBpcyBjYWxjdWxhdGVkIGJ5IGFkZGluZyB0aGUgcHJldmlvdXMgdHdvIG51bWJlcnMgb2YgdGhlIHNlcXVlbmNlLiBUaGUgZmlyc3QgdHdvIG51bWJlcnMgaW4gdGhlIEZpYm9uYWNjaSBudW1iZXIgYXJlIDAgYW5kIDEuPFwvcD5cclxuXHJcbjxwPlRoZSBzZXF1ZW5jZSZuYnNwO0ZuIG9mIEZpYm9uYWNjaSBudW1iZXJzIGlzIGRlZmluZWQgYnkgdGhlIHJlY3VycmVuY2UgcmVsYXRpb246IEY8c3ViPm48XC9zdWI+ID0gRjxzdWI+bi0xPFwvc3ViPiArIEY8c3ViPm4tMjxcL3N1Yj4gKG4gJmdlOyAyKS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gaW50ZWdlciBuLCB3cml0ZSBhIHByb2dyYW0gd2hpY2ggcHJpbnRzIG50aCBGaWJvbmFjY2kgbnVtYmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMmbmJzcDtvbmUgaW50ZWdlciZuYnNwO24uICgxICZsZTsgbiAmbGU7IDkwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgbGluZSBvZiBvbmUgaW50ZWdlciwgbnRoIEZpYm9uYWNjaSBudW1iZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

---

내가 푼 답

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

def fib2(n):
    f = [0]*(n+1)
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        f[1] = 1
        for i in range(2,n+1):
            f[i] = f[i-1] + f[i-2]
            return f[n]
def main():
    a = int(input())
    print(fib2(a))

if __name__ == '__main__':
    main()

---

참고할만한 소스

N = int(input())
dp = [0,1]

for i in range(2,n+1):

    dp.append(dp[i-1] + dp[i-2])  <--와;;

print(dp[-1])          <--와