[알고리즘 기초 100제] 2. 피보나치 수열

✔️문제

피보나치 수열을 출력해라.

- An = An-1 + An-2

- 1 1 2 3 5 8 13 21 34....

---

📍정답

package dya02;

public class Main {

  public static void main(String[] args) {

    //1번째 방법-배열
    int[]arr = new int[100];

    //An = An-1 + An-2; n>=3
    //a1 = 1, a2 = 1

    arr[0] = 1;
    arr[1] = 1;

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

    for(int i=0;i<10;i++) {
      System.out.print(arr[i]+" ");
    }

    //2번째 방법-이전숫자기억
    System.out.println();
    int prevPrevNum = 1; //An-2
    int prevNum = 1;     //An-1

    System.out.print(prevPrevNum+" ");
    System.out.print(prevNum+" ");

    for(int i=3;i<=10;i++) {
      int nNum = prevPrevNum+prevNum;
      System.out.print(nNum+" ");

      prevPrevNum = prevNum;
      prevNum = nNum;
      
    }
  }
}