Java으로 구현한 1003번 피보나치 함수 문제 풀이입니다.
https://www.acmicpc.net/problem/1003
import java.util.*;
import java.io.*;
public class Main {
static List<Integer> zero = new ArrayList<>();
static List<Integer> one = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
zero.add(1);
zero.add(0);
zero.add(1);
one.add(0);
one.add(1);
one.add(1);
for (int i=0; i<t; i++) {
int n = Integer.parseInt(br.readLine());
fibo(n);
}
}
public static void fibo(int num) {
int len = zero.size();
if (num >= len) {
for (int i=len; i<=num; i++) {
zero.add(zero.get(i-1) + zero.get(i-2));
one.add(one.get(i-1) + one.get(i-2));
}
}
System.out.println(zero.get(num) + " " + one.get(num));
}
}
1. 입력받은 num의 zero 사용 개수는 zero[i-1] + zero[i-2]와 같다.
0일때 : 1개
1일때 : 0개
2일때 : 1개
3일때 : 1개
2. 마찬가지로 num의 one 사용 개수는 one[i-1] + one[i-2]와 같다.
0일때 : 0개
1일때 : 1개
2일때 : 1개
3일때 : 2개
3. 따라서 구하고자 하는 대상(num)이 현재의 zero 개수보다 클 경우 length부터 num까지 각 zero의 개수, one의 개수를 구하여 각 리스트에 추가한다.
4. 최종적으로 num을 대상으로 사용한 zero의 개수, one의 개수를 출력한다.
'백준(JAVA) 풀이 > 다이나믹 프로그래밍' 카테고리의 다른 글
백준(JAVA) 1149번 RGB거리 풀이 (0) | 2022.09.16 |
---|---|
백준(JAVA) 2579번 계단 오르기 풀이 (0) | 2022.04.26 |
백준(JAVA) 1912번 연속합 풀이 (0) | 2022.04.25 |
백준(JAVA) 11054번 가장 긴 바이토닉 부분 수열 풀이 (0) | 2022.04.23 |
백준(JAVA) 11722번 가장 긴 감소하는 부분 수열 풀이 (0) | 2022.04.21 |