728x90
반응형
문제
https://www.acmicpc.net/problem/1003
풀이 방법
dp를 활용한 피보나치 관련된 문제다.
재귀호출을 사용해서 피보나치 수열을 구현할 때 0과 1을 호출하는 횟수를 출력해야한다.
그래서 dp배열은 [수][0과1호출수]을 담을 2차원 배열로 선언해줬다.
0일 때는 0호출 한번, 1일때는 1호출 한번이기 때문에 각각 1로 초기화해주고,
입력값의 최대값이 40이였기 때문에 나는 미리 40까지 다 구해주고, n에 따라서 출력해서 사용했다.
2부터 40까지 반복문을 돌리면서 i-1, i-2의 0과 1 호출 횟수를 더한 값을 각각 dp[n]에 저장해줬다.
그 이유는 재귀호출로 피보나치 수열을 구현했을때 처음부터 생각해보자. 그러면
f(2) = f(1) +f(0) 부터 시작할 것이다. 이 경우에는 f(1)은 1을 호출하고 1반환, f(0)은 0호출 후 0을 반환한다.
그러면 f(2)는 1호출 1회, 0호출 1회의 경우를 갖게 된다.
이어서
f(3) = f(2) +f(1) 인 경우를 보면
f(2)은 위에서 1호출 1회, 0호출 1회를 구했고,
f(1)은 1호출 1회, 0호출 0회이기 때문에
f(3)은 1호출 2회 , 0호출 1회를 갖게 된다.
이런식으로 값을 40까지 넣어주게 되는 것이다.
제출 코드
import java.io.*;
import java.util.*;
public class BJ_1003_피보나치함수 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[][] dp = new int[41][2];
dp[0][0] = 1;
dp[1][1] = 1;
for (int i = 2; i <= 40; i++) {
dp[i][0] =dp[i-1][0]+ dp[i-2][0];
dp[i][1] =dp[i-1][1]+ dp[i-2][1];
}
for (int test_case = 1; test_case <= T; test_case++) {
int n = Integer.parseInt(br.readLine());
System.out.println(dp[n][0] +" "+dp[n][1]);
}
}
}
728x90
반응형
'알고리즘 > BJ' 카테고리의 다른 글
[BJ] 백준 2579 계단 오르기 (JAVA) (0) | 2022.04.20 |
---|---|
[BJ] 백준 2748 피보나치 수2 (JAVA) (0) | 2022.04.13 |
[BJ] 백준 1012 유기농 배추 (JAVA) (0) | 2022.03.30 |
[BJ] 백준 1065 한수 (JAVA) (0) | 2022.03.28 |
[BJ] 백준 13458 시험감독 (JAVA) (0) | 2022.03.27 |