PS
백준 1788. 피보나치 수의 확장
tose33
2022. 11. 21. 14:29
https://www.acmicpc.net/problem/1788
1788번: 피보나치 수의 확장
첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
N이 양수일때는 그냥 피보나치와 동일하다.
음수일때는 N을 양수로 바꾸고 점화식이 d[i] = d[i-2] - d[i-1] 이 된다.
다른 분들 코드를 보니 음수일때를 구할 필요가 없다.
음수는 i가 짝수일때는 그냥 양수일 경우에서 - 만 붙여 주면 된다.
| i | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 |
| d[i] | -3 | 2 | -1 | 1 | 0 | 1 | 1 | 2 | 3 |