백준 : 피보나치 함수(1003) with 자바

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

피보나치 함수의 입력값이 주어졌을 때 0과 1이 몇번호출 되었는지 개수를 구하는 문제이다.

입출력을 살펴보자.

예제 입력 1 복사

3
0
1
3

3개의 n값 0,1,3을 입력받아 0과 1의 개수를 출력하면 된다.

0 -> 당연히 0호출 0 ->1, 0

1 -> 당연히 1호출 0 -> 0, 1

3 -> 2, 1 호출 -> 2가 다시 1,0호출 -> 1, 2

 

위 계산을 보면 점화식이 보인다. dp[i] = dp[i - 1] + dp[i - 2]

점화식이 나왔으니 바로 코드를 짜보자.

 

시간 초과 코드

package 연습;

import java.util.Scanner;

public class practice {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int t = sc.nextInt();
        int[] dp = new int[41];
        dp[1] = 1;
        for(int i = 2; i < 41; i++){
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        for(int i = 0; i < t; i++){
            int n = sc.nextInt();
            if(n == 0){
                sb.append("1 0\n");
                continue;
            }
            sb.append(dp[n - 1] + " " + dp[n] + "\n");
        }
        System.out.println(sb.toString());
    }
}

스캐너 객체를 생성하여 짰더니 시간초과가 나서 BufferedReader, BufferedWriter, StringBilder를 사용해서 다시 짜보았다.

 

package 동적프로그래밍;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class 파보나치함수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        int[] dp = new int[41];
        dp[1] = 1;

        for (int i = 2; i < 41; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                bw.write("1 0\n");
            } else {
                bw.write(dp[n - 1] + " " + dp[n] + "\n");
            }
        }
        bw.flush();
    }
}

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int t = Integer.parseInt(br.readLine());

일단 BufferedReader, BufferedWriter, StringBilder를 선언해준다.

그리고 입력받을 테스트 케이스의 개수 t를 입력받는다.

int[] dp = new int[41];

dp배열을 생성하고 "N은 40보다 작거나 같은 자연수 또는 0이다."라는 조건이 있었으므로 41로 크기를 지정해 주었다.

dp[1] = 1;

for(int i = 2; i < 41; i++){

      dp[i] = dp[i - 2] + dp[i - 1];

}

dp[1] = 1로 초기화를 해준뒤 위에서 구했던 점화식을 사용하여 dp[i]를 구해준다.

 

for (int i = 0; i < t; i++) {

       int n = Integer.parseInt(br.readLine());

       if (n == 0) {

            bw.write("1 0\n");

       }

       else {

             bw.write(dp[n - 1] + " " + dp[n] + "\n");

}

}

n의 크기를 입력받고 n이 0이면 1 0을 출력하고 n이 0이 아니라면 dp[n -1 ] dp[n]을 한 뒤 반복문을 탈출할 때까지 위과정을 반복해주었다.

 

위과정을 마치면 피보나치 함수의 최솟값을 구할 수 있을 것이다