백준 2747 [피보나치수]

import java.util.*;

public class Main{
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
        System.out.print("몇번째 피보나치수?");
         int n=sc.nextInt();
         int n1=0;
         int n2=0;
         int temp1=0;
         int temp2=0;
         
         for(int i=0;i<n;i++) {
             if(i==0||i==1) {
             	n1=n2;n2=1;
             }
             else {
                 temp1=n1;
                 temp2=n2;
                 n1=temp2;
                 n2=temp1+temp2;
             }
         }        
         System.out.println(n+"번째 피보나치 수는 "+n2);
	}
}

코세라의 알고리즘 파트1 강의를 오늘 처음 들어봤는데, 첫 주제가 dynamic connectivity였다. 강의만 들을 땐 그래도 이해가 좀 되고 흥미가 있었는데,

백준알고리즘에서  다이나믹 프로그래밍 카테고리에서 문제를 풀어봤는데 너무 어려웠다...

변수선언하는 것부터가 난관이었다...

좀 부끄럽기까지 하다.

다른 블로그의 코딩을 참고해서 어찌저찌 이해는 했지만, 이따가 다시한번 더 풀어봐야겠다...!

---

몇번째의 피보나치 수를 구하기 위해 변수를 몇개 사용해야 할까 생각해 봤다. 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

Fn = Fn-1 + Fn-2 (n ≥ 2)

• Fn-1 [n1]와 Fn-2 [n2] , 두개
• Fn, 그 둘을 더한 값이 들어갈 변수 하나 [tmp]

총 3개가 필요하다.

그래서 짠 코드는

import java.util.*;

public class Main{
	public static void main(String args[]){
		Scanner in=new Scanner(System.in);
		System.out.print("몇번째 피보나치수?");
		int n = in.nextInt();
		
		int n1=0;
		int n2=0;
		int tmp;
		
		for(int i=0; i<n; i++) {
			 if(i==0||i==1) {
				 n1=n2;
				 n2=1;
			  }
			 else {
				 tmp=n1+n2;
				 n1=n2;
				 n2=tmp;
			 }
		}

		System.out.println(n+"번째 피보나치 수는 "+n2);
		in.close();
	}
}	

블로그에서 참고한 코드보다 변수가 하나 줄일 수 있는 코드를 만든 것 같다!