https://www.acmicpc.net/problem/24416
24416번: 알고리즘 수업 - 피보나치 수 1
오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍
www.acmicpc.net
이번 문제는 해당 함수의 재귀가 얼마나 이루어지는 지에 대한 수를 구하는 문제이다.
풀이는 아래와 같다.
소스코드 1
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main
{
static int N1 = 0;
static int N2 = 0;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
fib(N);
fibonacci(N);
System.out.println(N1+ " " +N2);
}
public static int fib(int N)
{
if(N == 1 || N == 2)
{
N1++;
return 1;
}
else
{
return fib(N-1) + fib(N-2);
}
}
public static int fibonacci(int N)
{
// 0 ~ N까지 생성
int[] arr = new int[N+1];
// 3부터 생성하니까 0은 고려안해도 됨
arr[1] = arr[2] = 1;
for(int i=3;i<=N;i++)
{
N2++;
arr[i] = arr[i-1] + arr[i-2];
}
return arr[N];
}
}
추가로 다른 재미있는 풀이도 있어 가져왔다.
N1 은 1을 더하는 수이기 때문에 피보나치의 결과 값을 가져오면 되고,
N2 에 해당하는 fibonacci 는 위의 풀이와 같이 for문이 3부터 N까지 발생한다. 즉 N-2 를 구하면 된다는 의미이다.
소스코드2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main
{
static int N1 = 0;
static int N2 = 0;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
System.out.println(fibonacci(N)+ " " +(N-2));
}
public static int fibonacci(int N)
{
int[] arr = new int[N+1]; // 0 ~ N까지 생성
arr[1] = arr[2] = 1; // 3부터 생성하니까 0은 고려안해도 됨
for(int i=3;i<=N;i++)
{
N2++;
arr[i] = arr[i-1] + arr[i-2];
}
return arr[N];
}
}