1788. [Python]피보나치 수의 확장

1. 문제

 

https://www.acmicpc.net/problem/1788

1788번: 피보나치 수의 확장

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 다이나믹 프로그래밍

 

3. 파이썬 코드

 

def fibonacci(num):
    # 양수일때 피보나치 리스트
    dp = [0, 1]
    # 음수일 경우 피보나치 리스트
    dp_ma = [0, 1, -1]
    # 음수에서 절대값 구하기 위해서 사용되는 변수
    check = 0
    # n 값이 1000000을 넘지 않는다 했으므로 범위를 미리 설정하여 값을 다 구해둔다
    for _ in range(2,1000001):
        # 양수인 경우 기존의 피보나치 구하는 방식대로 구한다.
        answer_dp = dp[-1] + dp[-2]
        # 음수의 경우 기존에서 구하는 방식과는 다르게 -2 값에서 -1을 빼는 식으로 값을 구한다.
        answer_ma = dp_ma[-2]-dp_ma[-1]
        # 양수의 경우 그냥 나머지를 나눠서 값으로 넣어준다.
        answer_dp %= 1000000000
        # 만약 결과값이 음수인 경우 check 라는 변수에 1을 넣어주고 answer_ma에 -를 붙여서 양수로 변경해준다.
        if answer_ma < 0:
            answer_ma = -answer_ma
            check = 1
        # 똑같이 1000000000을 나눠준다
        answer_ma %= 1000000000
        # 만약 앞에서 check를 통해서 음수에서 양수로 변경되었다면 다시 음수로 바꿔준 후 check를 다시 0으로 바꾼다.
        if check == 1:
            answer_ma = -answer_ma
            check = 0
        dp.append(answer_dp)
        dp_ma.append(answer_ma)
    # 들어온 input 값에 따라서 반환해주는 리스트를 다르게 해준다.
    if num < 0:
        return dp_ma[abs(num)]
    else:
        return dp[num]

num = int(input())
ans = fibonacci(num)
# 반한된 결과값에 따라서 음수면 -1 양수면 1 0이면 0을 출력해준다.
if ans < 0:
    print(-1)
    print(abs(ans))
elif ans > 0:
    print(1)
    print(ans)
else:
    print(0)
    print(ans)

 

4. 문제를 풀고난 후 생각

 

• 문제를 보고 그냥 피보나치 수열을 구하면 되는게 아닌가? 라는 생각을먼저 했다. 그래서 기존의 피보나치 수열을 구현했고 input 으로 들어온 값이 음수인지 0인지 양수인지 등을 판단해서 첫째 값을 출력해 주었다.
• 틀리고 나서 문제를 보고 다시 생각을 했고, 음수로 들어온 input 값의 경우 피보나치 수열을 계산을 따로 해줘야 하고 그 인덱스 번호의 값이 양수인지 음수인지 0 인지를 판단해서 답을 출력하는 문제였다는 것을 깨달았다.
• 음의 피보나치를 어떻게 구현할지 고민을 했고, 기존의 더해가는 방식이 아닌 -2 인덱스에서 -1 인덱스를 빼주는 식으로 값을 추가해 나갔으며 출력을 구현하는 부분에서 음수이면 check 라는 변수를 통해서 -에서 +로 변해준 것을 체크해주며 값을 갱신해주었다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 다이나믹 프로그래밍