1003번 '피보나치 함수'

import java.io.*;

class Main{

static long[] dZero;

static long[] dOne;

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

StringBuffer stringBuffer = new StringBuffer();

int cases = Integer.parseInt(in.readLine());

int[] values = new int[cases];

for(int i=0;i<cases;++i)

values[i] = Integer.parseInt(in.readLine());

for(int i=0;i<cases;++i) {

int value = values[i];

dZero = new long[value+1];

dOne = new long[value+1];

stringBuffer.append(solve0(value));

stringBuffer.append(" ");

stringBuffer.append(solve1(value));

stringBuffer.append("\n");

}

System.out.println(stringBuffer);

in.close();

}

static long solve0(int n) {

if(n == 0)

return 1;

else if(n == 1)

return 0;

else if(dZero[n] > 0)

return dZero[n];

dZero[n] = solve0(n-1) + solve0(n-2);

return dZero[n];

}

static long solve1(int n) {

if(n == 0)

return 0;

else if(n == 1)

return 1;

else if(dOne[n] > 0)

return dOne[n];

dOne[n] = solve1(n-1) + solve1(n-2);

return dOne[n];

}

}

피보나치 수를 구하는 과정을 써내려가다 보면 0과 1의 빈도수에도 피보나치 수를 구하는 과정과 비슷하다는 것을 알 수 있다.

0과 1 각각에 대한 경우를 저장할 배열을 만들고 다이나믹 프로그래밍을 푸는 방법을 적용하였다.