이번 문제는 Fibonacci 수의 특정값까지의 합을 구하는 문제입니다. 하지만 여기에는 조건이 몇가지 있습니다. 단순히 해당 문제를 풀기위한 방법과, Algorithm 문제를 푸는 방식으로 여러개의 Test_Case가 들어오고 약간 도전적인 목표의 특정값을 해결할 수 있도록 해보겠습니다.
1. 주어진 조건의 문제 해결
제약조건은 아래와 같습니다.
- 400만 이하의 Fibonacci를 대상으로 함
- 그 중에서 짝수인 값의 합을 구함
저는 우선 Fibonacci가 400만까지 가려면 얼마나 많은 단계를 거쳐야 하는지 궁금해졌습니다. 그래서 관련 코드를 대충 짜보면...
a, b = 1, 2
cnt = 0
while True:
temp = a + b
if temp > 4000000: break
print(temp)
a = b
b = temp
cnt += 1
print(cnt)은근 cnt가 클거라고 생각했는데...
3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 (총 30개) 밖에 안되네요...;;
그럼 그냥 짝수만 더해볼까요??
a, b = 1, 2
res = 2
while True:
temp = a + b
if temp > 4000000: break
a = b
b = temp
if b & 1 == 0: res += b
print(res)
2. 도전적인 목표 해결
보통 Alogithm 문제들은 제약조건이 Test_Case 몇개에 최대가능한 input 값이 지정되고 응답시간이 몇초이내... 이렇게 되어있습니다. 그래서 유사하게 만들어 보겠습니다.
- Test_Case <= 10000
- Max Input Target <= 4e16
이번에는 최대치가 무려 4의 16승입니다. 그럼 이걸 넘어서기까지 Fibonacci가 몇단계까지 가야할까요??
a, b = 1, 2
cnt = 0
while True:
temp = a + b
if temp > 4e16: break
a = b
b = temp
cnt += 1
print(cnt)78단계 입니다.
Test_Case가 10000개나 되고, 매번 Test_Case마다 해당 숫자까지 Fibonacci를 계산한다면 비효율 적이라고 생각됩니다. 물론 해당 제약조건을 해결하는데는 큰 효율을 기대하긴 어렵겠지만요... 그래서 저는 Fibonacci를 한번에 계산해 놓고 각 Test_Case마다 계산해 놓은 결과에 짝수만 찾아서 더하기로 하겠습니다.
def preCalcFibo():
res = [1, 2]
for i in range(2, 100):
temp = res[i-2]+res[i-1]
if temp > 4e16: break
res.append(temp)
return res
if __name__ == '__main__':
fiboList = preCalcFibo()
tc = int(input())
for i in range(tc):
targetNo = int(input())
ans = 0
for i in range(len(fiboList)):
if fiboList[i] & 1 == 0 and fiboList[i]<=targetNo:
ans += fiboList[i]
print(ans)저는 이렇게 해결해 보았습니다. 다른분들은 어떻게 해결하셨을지 궁금하네요~
-Ayotera Lab-
댓글