dp2 [백준] 2748번: 피보나치 수 2 [JAVA-자바] 문제 www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net Problem 피보나치를 구하는 가장 기본적인 DP 문제이다. 메모제이션을 안쓰면 시간복잡도 O(2^N) 메모제이션을 쓰면 시간복잡도 O(N) Solution DP를 이용해서 문제를 해결한다. Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im.. 2021. 1. 12. [백준] 1003번: 피보나치 함수 [JAVA-자바] 문제 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net Problem 0.25초라는 시간 제한이 있기 때문에 시간을 신경써야 하는 문제 문제 그대로 단순하게 구현하면 무조건 시간 초과가 발생한다. 연상량을 줄이기 위해서는 메모제이션을 써야 한다. 메모제이션을 안쓰면 시간복잡도 O(2^N) 메모제이션을 쓰면 시간복잡도 O(N) Solution DP를 이용해서 문제를 해결한다. 피보나치 값이 0과 1일때는 바로 "1 0", "0 1" 로 출력한다. dp[][] 배열을 만들어서 0과 1을 따로 카운트 한다. 현재값은 전의값과 전전값이 합쳐진 값이기 때문에 아래와.. 2021. 1. 12. 이전 1 다음
