백준 1003번 피보나치 함수 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.25 초 (추가 시간 없음)

128 MB

176402

51239

40178

31.870%

문제

다음 소스는 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

풀이

해당 문제는 다이나믹 프로그래밍으로 풀이하는 문제이다.

다이나믹 프로그래밍은 재귀용법과 관련지어서 생각해볼수 있는데,

재귀용법은 단순히 매 문제마다 더이상 풀 수 없을때까지 풀이하고 넘어간다면

다이나믹 프로그래밍은 메모이제이션 기법을 활용해서 매 문제의 답을 기억해두고 다음 문제를 풀이할때 그 답을 참고하여 풀이한다는 것이다.

 

기본적인 풀이에는 배열을 생성해 사용하는데,

 

해당 문제또한 마찬가지로 배열을 사용해 풀이할 수 있다.

그리고 작은 단계부터 점점 풀어나가서 답을 찾는 방식으로 풀이하면 된다.

 

 

일단 단순히 바로 답을 구할 수 있는 것들은 답을 저장해둔다.

값이 0이 들어오면 0을 반환하고, 1이 들어오면 1을 반환한다고 문제에 친절하게 힌트가 적혀있다.

해당 문제는 0이나 1을 몇번 출력하는지를 알고싶어하고, 40보다 작거나 같은 수라고 하니 0부터 40 , 즉 41개의 공간을 가진 배열을 생성해

미리 0과 1이 들어올때의 답을 배열에 넣어놓는다.

        Integer[][] arr = new Integer[41][2];
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 0;
        arr[1][1] = 1;

0일때 0이 반환되니 0번째의 0은 1, 1은 출력되지 않으니 0이 된다.

1일때는 0이 반환되지 않고 1만 반환되니 0 , 1 이 되는것이다.

0 과 1 의 답을 제시해주고 있으니 2부터 반복문을 돌려서  N번 반복하는 반복문을 실행하면 된다.

여기서 메소드를 호출하지 않고 배열로만 계산을 진행한다.

        for (int j = 0; j < N; j++) {
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
            arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
        }

여기서 엄청 헷갈릴것이다.

피보나치를 머릿속으로 그리는것도 어려운데.. 반복문으로 저렇게 표현하고 있으니..

arr[i][0]  <- 이것은 피보나치(2)를 했을때 0이 출력되는 횟수가 된다.

arr[1][0] 은 아까 위에서 선언했듯이 0이 될것이고, arr[0][0]은 1이 된다.

 

그렇다.. 이것은 피보나치 함수의 결과값을 제출해야 하는것이 아닌 피보나치 함수(N) 을 실행했을때 1과 0이 몇번 출력되는지를 구하는것이다..!

 

package baekjoon.a1003;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class a1003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Integer[][] arr = new Integer[41][2];
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 0;
        arr[1][1] = 1;
        for (int j = 0; j < N; j++) {
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
            arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
        }
            System.out.println(arr[n][0]+" "+arr[n][1]);
    }
    }

}

이렇게만 풀이하면 어렵게 생각하지 않고 풀이할 수 있다.