[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)1003번, 피보나치 함수

문제 링크

1003번: 피보나치 함수

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

위 문제에서는 피보나치 수에 대한 연산을 지속적으로 반복하고 있으며 이전에 연산한 값도 여러번 반복하는 것을 볼 수 있습니다.

위 문제예시처럼 n이 3인경우 피보나치 수가 2일때, 1일때, 0일 때를 반복하는 것을 볼 수 있습니다.

그래서 처음에 해당하는 연산값을 따로 저장한 뒤에 똑같은 연산을 실행하기전 저장한 연산값을 가져와서 연산을 실행하지 않고 진행하는 것입니다.

피보나치 연산 값 저장 배열은 N이 최대 40이하이므로 41만큼 배열 크기를 주었으며 지금 구해야하는 것이 0과 1의 개개수이므로 열의 크기는 2를 주었습니다.

 

처음에 배열을 int형으로 만들어서 진행하였지만 int형은 0으로 초기화되어 다시 음수로 초기화를 다시 진행해야 하다고 판단하여 중간에 Integer형으로 바꾸었습니다. Integer형은 초기화시 null값이기 때문에 그것을 이용하였습니다.

 

• 피보나치 연산 값 저장할 배열 fibonaciData을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 피보나치의 n=1,0일 때 횟수를 구하는 함수 fibonaci을 만들었습니다.
• 피보나치 연산값 초기화하는 함수 fibonaciInit를 만들었습니다.

• fibonaciData가 null이면 연산값이 저장이 안된 것으로 연산을 진행한다.
• null이 아닌 경우 한 번 연산한 값이 저장되어 있으므로 저장된 값을 반환한다.
• 위에 알고리즘을 토대로 sudokuSolution을 작성하였습니다.

결과 코드

import java.io.*;
public class Main{
	static Integer[][] fibonaciData = new Integer[41][2];	//피보나치 연산값 저장 배열
	static int size;	//입력 횟수
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //----------------입력값 저장 및 함수 실행----------
    	size = Integer.parseInt(br.readLine());
    	fibonaciDataInit();
    	for(int i=0;i<size;i++) {
    		int num = Integer.parseInt(br.readLine());
    		fibonaci(num);
            //결과 출력
    		System.out.println(fibonaciData[num][0] + " " + fibonaciData[num][1]);
    	}
    	br.close();
	}
    //---------------피보나치 함수 구하기-------------
	public static Integer[] fibonaci(int n) {
		if(fibonaciData[n][0]==null || fibonaciData[n][1]==null) {
			fibonaciData[n][0] = fibonaci(n-1)[0] + fibonaci(n-2)[0];
			fibonaciData[n][1] = fibonaci(n-1)[1] + fibonaci(n-2)[1];
		}
		return fibonaciData[n];
	}
    //----------피보나치 수 저장 배열 초기화------------
	public static void fibonaciDataInit() {
    	fibonaciData[0][0]=1;	//n=0일 때 0의 개수
    	fibonaciData[0][1]=0;	//n=0일 때 1의 개수
    	fibonaciData[1][0]=0;	//n=1일 때 0의 개수
    	fibonaciData[1][1]=1;	//n=1일 때 1의 개수
	}
}