[BOJ] #DP - 9607번 Generations of Tribbles (JAVA)

문제 출처 : https://www.acmicpc.net/problem/9507

기존 피보나치보다 조금 더 복잡한 피보나치를 구현하는 문제.

오늘 정리한 다이나믹 프로그램을 적용하기에 딱 좋은 기초 문제였다.

입력 첫 줄에 테스트 케이스 수가 주어진다 하여 MEMOZATION 기법을 이용 할 목적으로 전역 변수를 선언 하였다.

static long[] fib = new long[68];

<참고>

int는
-2147483648 ~ 2147483647
long은
-9223372036854775808 ~ 9223372036854775807

다음으로 SOLUTION 함수를 작성 하였다. 기존의 B0TTOM-UP 방식으로 피보나치를 구현하는 것과 동일한 짜임(?)이다.

public static long koong(int n){

        if(fib[n] != 0){

            return fib[n];

        }

        fib[0] = 1;

        fib[1] = 1;

        fib[2] = 2;

        fib[3] = 4;

        for(int i = 4; i <= n; i ++) {

            fib[i] = fib[i-1] + fib[i-2] + fib[i-3] + fib[i-4];

        }

        return fib[n];

    }

아래는 전체 코드이다.

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

public class Main 
{
	static long[] fib = new long[68];
	
    public static void main( String[] args ) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int length = Integer.parseInt(br.readLine());
		for(int i = 0; i < length; i++){
			System.out.println(koong(Integer.parseInt(br.readLine())));
		}
	}

	//Dynamic Programming 
	public static long koong(int n){
		if(fib[n] != 0){
			return fib[n];
		}

		fib[0] = 1;
		fib[1] = 1;
		fib[2] = 2;
		fib[3] = 4;

		for(int i = 4; i <= n; i ++) {
			fib[i] = fib[i-1] + fib[i-2] + fib[i-3] + fib[i-4];
		}
		return fib[n];
	}
}

그런데 문제 풀이 후 다른 사람의 코드를 보고서는 아차 싶었다 ㅠㅠ

바로 저  KOONG 함수를 한번만 사용 해도 된다는점!

애초에 피보나치 수열을 67번째 값 까지 한번만 구해 두고 그 다음 테스트 케이스를 받아서 N번째 인덱스를 출력하기만 하면 더 간단하게 해결 할 수 있었다...

분발해야지 ㅠㅠ