백준 1003번 : 피보나치 함수

박찬규·2023년 3월 28일
0

처음 봤을때 피보나치 함수를 구현해서 돌렸으나 시간 초과가 났고,
메모이제이션을 사용했으나 여전히 시간 초과가 났다.
몇번의 삽질 끝에 힌트를 봤고,

n 0 1 2 3 4 5 6 7
0 출력횟수 1 0 1 1 2 3 5 8
1 출력횟수 0 1 1 2 3 5 8 13
다음과 같은 규칙성을 발견했다. 주어진 수가 n일 때,
{ 0의 출력 횟수 = (n-1) 일때의 1의 출력횟수 }였다.
이를 배열로 나타내면
dp[n] = n일때 1의 출력횟수,
dp[n-1] = n일때 0의 출력횟수와 같다. 이 아이디어를 코드로 나타내면 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        // dp[n] = 1의 출력횟수 dp[n-1] = 0의 출력횟수
        // 즉 dp[n] + dp[n-1] 을 구하면 됨.

        int[] dp = new int[41];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                System.out.println("1 0");
                continue;
            }
            for (int j = 2; j <= n; j++) {
                dp[j] = dp[j-1] + dp[j-2];
            }

            System.out.printf("%d %d\n", dp[n-1], dp[n]);
        }
    }
}

0개의 댓글