[백준/1788] 피보나치 수의 확장 (Python)

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

1788번: 피보나치 수의 확장

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:20:57

 

---

 

문제 설명

 

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

 

입력 및 출력

 

입력

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

 

출력

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

 

입력 예시

-2

 

출력 예시

-1
1

 

 

---

 

풀이

 

..나중에 생각해보니, 꼭 이런 식으로 풀 필요는 없었던 것 같다....

 

피보나치 수열, 그 중에서 이런 식으로 상대적으로 적은 값은 DP를 이용해 시간초과 없이 연산 가능하다. (내가 사용한 방식은 예전에 다루었던 행렬 제곱을 이용한 방식이다). 음수일 때는 Fn-2 = Fn - Fn-1 점화식을 이용해 구할 수 있다.

 

풀이 코드

N = int(input())
MOD = 1000000000
def matmul(a, b) :
  result = list()
  for i in range(2) :
    tmp = list()
    for j in range(2) :
      _tmp = 0
      for k in range(2) :
        _tmp = _tmp + a[i][k]*b[k][j]
      tmp.append(_tmp)
    result.append(tmp)
  return result

def matpow(mat, p) :
  if p == 1 :
    return mat

  _mat = matpow(mat, p//2)
  pmat = matmul(_mat, _mat)
  if p % 2 :
    return matmul(pmat, mat)
  else :
    return pmat

def cal_result() :
  if N == 0 :
    return (0, 0)
  if N == 1 or N == -1 :
    return (1, 1)

  if N < 0 :
    mat = [[-1, 1], [1, 0]]
    a, b, p = 0, 1, abs(N)
  else :
    mat = [[1, 1], [1, 0]]
    a, b, p = 1, 0, N-1

  mat = matpow(mat, p)
  result = a*mat[0][0] + b*mat[0][1]
  ab_result = 1 if result > 0 else (-1 if result < 0 else 0)
  return (ab_result, abs(result) % MOD)

ab_result, result = cal_result()
print(ab_result)
print(result)

풀이 완료..!