[백준(Baekjoon)][자바(java)] 2749 : 피보나치 수 3 / 분할 정복

 

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

2749번: 피보나치 수 3

 

* 피보나치 수

 

 

1. 동적 계획법 ( Dynamic Programming )

 

- 하향식 ( top-down )

import java.util.Scanner;

public class Main {

	public static int dp[], p = 1000000;
	
	public static int Fibo( int n ) {
		if( n == 0 || n == 1 )	return n;
		else if( dp[n] != 0 )	return dp[n] % p;
		else 					return dp[n] = ( Fibo(n-1) + Fibo(n-2) ) % p;
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		dp = new int[num+1];
		sc.close();
        
		System.out.println( Fibo( num ) );
		
	}
}

 

- 상향식 ( bottom-up )

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt(), p = 1000000;
		sc.close();

		long a = 0, b = 1, c = 0;
		if( num == 0 || num == 1 ) {
			System.out.println( num );
			return;
		}
		for( int i = 2; i <= num; i++ ) {
			c = ( a + b ) % p;
			a = b % p;
			b = c % p;
		}
			
		System.out.println( c );
	}
}

 

( 수가 커지면 1번 방법보다는 2번 방법이 효율적 )

 

 

2. 분할정복 ( Divide & Conquer )  -- 행렬의 곱셈을 이용

 

import java.util.Scanner;

public class Main {
	
	static final int p = 1000000;
	static long n, a[][] = { {1,1},{1,0} }, r[][] = new long[2][2];
	
	public static long[][] matrix_pow( long k ) {
    
		int i, j, l;
		if( k == 1 )	return r = a;
        
		long t[][] = matrix_pow( k / 2 );
        
		long t_e[][] = new long[2][2];
		for( i = 0; i < 2; i++ ) 
			for( j = 0; j < 2; j++ ) 
				for( l = 0; l < 2; l++ )
					t_e[i][j] += t[i][l] * t[l][j] % p;
		r = t_e;
		if( k % 2 == 1 ) {
			long t_o[][] = new long[2][2];
			for( i = 0; i < 2; i++ ) 
				for( j = 0; j < 2; j++ ) 
					for( l = 0; l < 2; l++ )
						t_o[i][j] += t_e[i][l] * a[l][j] % p;
			r = t_o;
		}
        
		for( i = 0; i < 2; i++ ) 
			for( j = 0; j < 2; j++ ) 
				r[i][j] %= p;
                
		return r;
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		n = sc.nextLong();
        
		matrix_pow( n );
        
		System.out.println( r[0][1] );
		sc.close();
	}
}