{% embed url=“https://www.acmicpc.net/problem/1003” %}
Solution. bottom-up
•
14056 kb / 124 ms
•
시간 제한이 0.25초로 굉장히 엄격한 조건이었다.
•
접근방식
◦
구해야 하는 것은 f(0)과 f(1) 이 호출된 횟수이다.
◦
0부터 차례대로 0과 1이 호출된 횟수를 쌍으로 나열해보니 피보나치 함수처럼 이전의 두 결과값을 더한 것이 현재의 결과값을 나타내는 구조를 파악할 수 있었다.
▪
f(3)에서 0이 호출된 횟수 = f(2)에서 0이 호출된 횟수 + f(1) 에서 0이 호출된 횟수
◦
따라서 피보나치 수열을 bottom-up 방식으로 구하도록 정의한 뒤, 매 연산의 결과를 배열에 저장하여 이전 연산 값을 참조할 수 있도록 하였다.
◦
그냥 피보나치수열보다 까다로웠던 점은, 0이 호출되는 횟수와 1이 호출되는 횟수 두 개를 각각 다른 배열에서 체크해야한다는 점이었다.
package practice.algorithm.dp;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;/** * https://www.acmicpc.net/problem/1003 * 14056 kb / 124 ms
* 피보나치 함수 * - 구해야하는 것 : f(0), f(1) 이 호출되는 각각 횟수 * */public class Bj1003 { private static int[] zero; private static int[] one; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while (t != 0) { int n = Integer.parseInt(br.readLine()); zero = new int[n+1]; one = new int[n+1]; fib(n); sb.append(zero[n]).append(" ").append(one[n]).append("\n"); t--; Arrays.fill(zero, 0); Arrays.fill(one, 0); } System.out.println(sb); } private static void fib(int n) { zero[0] = 1; if (n == 0) return; one[1] = 1; if (n == 1) return; for (int i = 2; i <= n; i++) { zero[i] = zero[i-1] + zero[i-2]; one[i] = one[i-1] + one[i-2]; } } /**n - v = (0 1) * 0 - 0 = 1 0 * 1 - 1 = 0 1 * 2 - 0+1 = 1 1 * 3 = 2 + 1 = 0+1 + 1 = 1 2 * 4 = 3+2 = 1 2 + 1 1 = 2 3 * 1, 0 * 0, 1 * 1, 1 * 1, 2 * 2, 3 * 3, 5 * 5, 8 * 8, 13 * 13, 21 * f(n) 까지의 0과 1의 호출 횟수 = f(n-1)까지의 횟수 + f(n-2)까지의 횟수 * */}
Java
복사