Baekjoon - 1003

문제

Solved.ac Class3

1차시도

public class Main {
	private static int zeroSize;
	private static int oneSize;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int size = Integer.parseInt(br.readLine());

		for (int i = 0; i < size; i++) {
			zeroSize = 0;
			oneSize = 0;
			fibonacci(Integer.parseInt(br.readLine()));
			sb.append(zeroSize).append(" ").append(oneSize).append("\n");
		}

		System.out.println(sb);
	}

	private static int fibonacci(int n) {
		if (n == 0) {
			zeroSize++;
			return 0;
		} else if (n == 1) {
			oneSize++;
			return 1;
		} else {
			return fibonacci((n - 1)) + fibonacci((n - 2));
		}
	}

}

시간초과

2차시도

있는 함수를 그대로 사용하면 시간초과가 발생한다
동적 프로그래밍으로 해결한다

public class Main {
	private static Integer[] array;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int size = Integer.parseInt(br.readLine());
		array = new Integer[41];
		array[0] = 0;
		array[1] = 1;
		for (int i = 0; i < size; i++) {
			int n = Integer.parseInt(br.readLine());
			if (n == 0) {
				sb.append("1 0\n");
			} else if (n == 1) {
				sb.append("0 1\n");
			} else {
				sb.append(fibonacci(n - 1)).append(" ").append(fibonacci(n)).append("\n");
			}
		}
		System.out.println(sb);
	}

	private static int fibonacci(int n) {
		if (array[n] == null) {
			array[n] = fibonacci(n - 1) + fibonacci(n - 2);
		}
		return array[n];

	}
}

성공

처음으로 동적 계획법을 사용했다.
생각보다는 좀 빡세다.