피보나치 함수
시간 제한메모리 제한제출정답맞힌 사람정답 비율
| 0.25 초 (추가 시간 없음) | 128 MB | 249766 | 80677 | 63941 | 34.256% |
문제
다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return fibonacci(n‐1) + fibonacci(n‐2);
}
}
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
- 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
- fibonacci(0)은 0을 출력하고, 0을 리턴한다.
- fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
- 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
예제 입력 1 복사
3
0
1
3
예제 출력 1 복사
1 0
0 1
1 2
예제 입력 2 복사
2
6
22
예제 출력 2 복사
5 8
10946 17711
출처
- 문제를 번역한 사람: baekjoon
- 데이터를 추가한 사람: connotation, doju, wonrok97
- 어색한 표현을 찾은 사람: cyj101366
알고리즘 분류
자.. 여기서 다이나믹 프로그래밍을 왜 쓰냐?
-> 저렇게 쪼개서 재귀 호출 하는 게 맞긴 함. 그치만 저러면은 이미 했던 계산도 계속 다시 하게 되겠쥬? 한 번 했던 계산은 다시 안 하는 게 좋은데..
그래서 출력 횟수를 저장해놓는 겁니다!
ㄴ네!
미리 저장해놓는다 + 어차피 0이랑 1횟수(0 1 출력... ) 만 저장하니까
미리 배열을 그 크기만큼 만들어놓고 저장하면 되겠다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[] count0 = new int[T];
int[] count1 = new int[T];
count0[0] = 0;
count0[1] = 0;
count1[0] = 1;
count1[1] = 0;
for (int i = 2; i < T; i++) {
count0[i] = count[i - 1] + count[i - 2];
count1[i] = count[i - 1] + count[i - 2];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
sb.append(count0[N]).append(" ").append(count1[N]).append("\n");
}
System.out.println(sb);
}
}
안녕하세요 컴파일 에러입니다.
흠냐아아
근데 다시 보니까 진짜 엉망진창임
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[] count0 = new int[41];
int[] count1 = new int[41];
count0[0] = 1;
count0[1] = 0;
count1[0] = 1;
count1[1] = 0;
for (int i = 2; i < T; i++) {
count0[i] = count0[i - 1] + count0[i - 2];
count1[i] = count1[i - 1] + count1[i - 2];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
sb.append(count0[N]).append(" ").append(count1[N]).append("\n");
}
System.out.println(sb);
}
}
배열 크기는 얘가 총 40까지 나올 수 있다 했으니까 41로 잡아야 했고, count 배열 잘못 씀(count0 안 쓰고 count)
이거 고쳣ㅎ더니
ㅎㅇ
배열 순회에서 문제 있는 듯
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[] count0 = new int[41];
int[] count1 = new int[41];
count0[0] = 1;
count0[1] = 0;
count1[0] = 1;
count1[1] = 0;
for (int i = 2; i < 41; i++) {
count0[i] = count0[i - 1] + count0[i - 2];
count1[i] = count1[i - 1] + count1[i - 2];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
sb.append(count0[N]).append(" ").append(count1[N]).append("\n");
}
System.out.println(sb);
}
}
다시 배열에 넣어줄 때도 41로 바꿈
틀렸다....
왜요
왜??
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[] count0 = new int[41];
int[] count1 = new int[41];
count0[0] = 1;
count0[1] = 0;
count1[0] = 0;
count1[1] = 1;
for (int i = 2; i < 41; i++) {
count0[i] = count0[i - 1] + count0[i - 2];
count1[i] = count1[i - 1] + count1[i - 2];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
sb.append(count0[N]).append(" ").append(count1[N]).append("\n");
}
System.out.println(sb);
}
}
보니까 초기값을 잘못 넣어줬다.
해결 완!!!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[] count0 = new int[41]; // 0~40 0 개수 세서 저장해줄 배열
int[] count1 = new int[41]; // 0~40 1 개수 세서 저장해줄 배열
count0[0] = 1; // 0은 0 개수 1개
count0[1] = 0; // 1은 0 개수 0개
count1[0] = 0; // 0은 1 개수 0개
count1[1] = 1; // 1은 1 개수 1개
// 2부터 시작 40까지 배열에 더해주기
for (int i = 2; i < 41; i++) {
count0[i] = count0[i - 1] + count0[i - 2];
count1[i] = count1[i - 1] + count1[i - 2];
}
// 출력
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
sb.append(count0[N]).append(" ").append(count1[N]).append("\n");
}
System.out.println(sb);
}
}'백준 풀기' 카테고리의 다른 글
| 백준 2579번: 계단 오르기 with Java (8) | 2025.06.08 |
|---|---|
| 백준 9095번: 1, 2, 3 더하기 with Java (0) | 2025.06.08 |
| 백준 1991번: 트리 순회 with Java (0) | 2025.05.18 |
| 백준 2178번: 미로 탐색 with Java (0) | 2025.05.11 |
| 백준 2606번: 바이러스 with Java (0) | 2025.05.04 |