[백준 1003번] 피보나치 함수(Java)

👩🏻‍💻  오늘은 오답노트를 적어볼까 한다 

틀린 코드가 창피하지만...! 이제 안틀리지 말자는 의미로 공개핑

 

문제

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

 

한 마디로 피보나치 수열을 계산하면서 0과 1의 호출 횟수를 출력하는 문제이다.

---

❌❌❌       틀린 코드

 

이 코드의 의도는 피보나치 수열 계산을 통해 0과 1의 호출 횟수를 누적하는 것이었다.

하지만 이 방식은 잘못된 호출 횟수를 반환한다.

➡️ 의도대로 동작하게 하려면 재귀 호출 패턴을 추적하는 방식이 필요하지만 어렵다.

실제 호출 횟수는 피보나치 수열에서 각 항이 다른 항들을 호출하는 횟수에 따라 달라진다.

---

🍀

개선해야 할 점

피보나치 수열에서 각 항이 다른 항들을 호출하는 횟수를 추적하려면

각 수가 호출되는 횟수를 따로 추적하는 배열이 필요하다.

 

점화식은 이전 값들의 합을 직접 계산해서 새로운 값으로 덮어쓰는 방식이기 때문에

+= 가 아닌 =를 사용하는 것이 적절하다.

 

 

💙

정답코드

import java.io.*;

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());

        int[] zeroCnt = new int[41];
        int[] oneCnt = new int[41];

        // 초기값 설정
        zeroCnt[0] = 1;
        oneCnt[0] = 0;
        zeroCnt[1] = 0;
        oneCnt[1] = 1;

        for(int i=2; i<=40; i++) {
            zeroCnt[i] = zeroCnt[i-1] + zeroCnt[i-2];
            oneCnt[i] = oneCnt[i-1] + oneCnt[i-2];
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(zeroCnt[N]).append(" ").append(oneCnt[N]).append("\n");
        }
        System.out.println(sb);
    }
}