1788 피보나치 수의 확장

 

 

양수, 음수를 나누어서 풀었는데,

 

일단 

 

f(0) = 0

f(1) = 1 

 

1) n : 양수

f(n) = f(n-1) + f(n-2) 이므로,

 

f(2) = f(1) + f(0) 

f(3) = f(2) + f(1) 

f(4) = f(3) + f(2)

 

여기에서, dp[i] = dp[i-1] + dp[i-2] 임을 알 수 있다.

 

 

2) n : 음수

 

f(n-2) = f(n) - f(n-1) 이므로

f(-1) = f(1) - f(0)

f(-2) = f(0) - f(-1)

f(-3) = f(-1) - f(-2)

 

이 경우, 절댓값으로 숫자 따지면,

dp[i] = dp[i-2] - dp[i-1] 이 된다.

 

그래서 양수의 경우는 dp_plus 배열로, 음수의 경우는 dp_minus 배열로 따로 만들었고,

음수의 경우에는 

-1 일 경우, f(1) 을 더해야 하므로, 양수와 관련되어 

dp_minus[1] = dp_plus[1] - dp_plus[0] = 1 값을 처음에 넣어주고,

dp_minus[2] 부터 계산하도록 하였다.

 

-------------------------------------

 

하지만 꼭 이렇게 풀지 않아도 되고,

따져보면

양수의 경우 

n	0	1	2	3	4	5
값	0	1	1	2	3	5

 

 

음수의 경우

 

n	0	1	2	3	4	5
값	0	1	-1	2	-3	5

 

이런식으로, 절댓값은 같고, 마이너스 부호가 붙는 경우의 차이만 생긴다는 것을 알 수 있다. 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
    
        int dp_plus[] =  new int[1000001];
        int dp_minus[] = new int[1000001];
        
        dp_plus[0] = 0;
        dp_plus[1] = 1;
        
        dp_minus[0] = 0; 
        dp_minus[1] = 1; 
       
        
        for(int i =2; i<=1000000; i++) {
        
        	dp_plus[i] = (dp_plus[i-1] + dp_plus[i-2])%1000000000;
        	dp_minus[i] = (dp_minus[i-2] - dp_minus[i-1])%1000000000;
        }              
   
        
        int result = 0;
        if(N>=0) {
        	result = dp_plus[N];
        }else {
        	result= dp_minus[Math.abs(N)];
        }
        
        if(result>0) {
        	System.out.println(1);
        	System.out.println(result);
        }else if(result ==0 ) {
        	System.out.println(0);
        	System.out.println(result);
        }else if(result<0) {
        	System.out.println(-1);
        	System.out.println(Math.abs(result));
        }
      
        
    }
}