[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)11444번, 피보나치 수 6

문제 링크

11444번: 피보나치 수 6

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

분할 정복 알고리즘은 일정한 간격으로 입력된 값을 분할하여 조건에 맞는지 확인하고 틀리면 다시 일정한 간격으로 분할하는 것을 반복하여 조건에 만족할 때까지 진행하는 알고리즘입니다.

행렬 곱셈의 원리와 피보나치 수 점화식을 행렬로 표현하는 방법을 알면 풀 수 있는 문제입니다.

먼저 행렬 곱셈에 대하여 알아보겠습니다.

행렬 곱셈 - 위키백과, 우리 모두의 백과사전

 

 

 

 

N × M의 배열과 M × K의 배열을 곱하면 N × K 크기의 배열이 만들어집니다.

N × K 배열의 값은 가로줄과 세로줄의 대응하는 값들의 곱을 모두 더한 값이 됩니다.

예를 들면

피보나치 수의 점화식을 행렬로 나타내는 과정을 살펴보도록 하겠습니다.

점화식

행렬의 형태로 표현하면

위와 같은 행렬식이 나옵니다.

| 1 1 |

| 1 0 |

n의 제곱한 결과 행렬에 [1][0]의 값을 가져오면 f(n)의 값을 얻을 수 있습니다.

n의 제곱을 할 때에는 분할 정복을 통해서

A⁴ = (A²)² = ((A)²)² 으로 재귀를 통해 분할 정복을 통해 행렬의 곱셈을 진행할 것입니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 행렬 제곱/행렬 곱셈을 구하는 arrPow/arrMul함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 배열[1][0]에 값이 f(n)의 값이므로 그 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• arrPow함수에서 재귀를 통하여 제곱의 형태로 만들었습니다.
• arrMul함수에서 행렬에 곱셈에 대한 공식을 알고리즘으로 3중 for문을 이용하여 만들었습니다.

 

결과 코드

import java.io.*;
public class Main{
	static int MOD = 1000000007;	//나머지 구하기 위해 나누는 값
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----------입력값 저장--------
        long N = Long.parseLong(br.readLine());
        if(N==0)	//입력값 0일 때
        	bw.write(0 + "\n");
        else {		//그 이외에
            long[][] arr = {{1,1},{1,0}};
            long[][] result = arrPow(arr, N);	//함수 실행
            bw.write((result[1][0] % MOD) + "\n");	//결과 BufferedWriter에 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //---------배열 제곱-----------
    public static long[][] arrPow(long[][] A, long N){
    	if(N==1)
    		return A;
    	
    	long[][] temp = arrPow(A,N/2);
    	
    	if(N%2==0) {	//계수가 짝수일 때
    		return arrMul(temp,temp);
    	}else {		//계수가 홀수일 때
    		return arrMul(arrMul(temp, temp), A);
    	}
    }
    //--------------배열 곱셈-----------
    public static long[][] arrMul(long[][] A, long[][] B){
    	long[][] temp = new long[2][2];
    	for(int i=0;i<2;i++) {
    		for(int j=0;j<2;j++) {
    			for(int k=0;k<2;k++) {
    				temp[i][j] += A[i][k] * B[k][j];
    				temp[i][j] %= MOD;
    			}
    		}
    	}
    	return temp;
    }
}