계단오르기

전략

 

다이나믹 table을 만든다

 

한번에 1 or 2번씩 올라갈 수 있을 때

1번 계단 오르는 방법 1

2번 계단 오르는 방법 2

 

3번 계단 오르는 방법, 1번계단에서 2칸 오르기 or 2번 계단에서 1칸 오르기

따라서 3번계단 오르는 방법 = 1번 계단오르는 방법 + 2번 계단 오르는 방법

 

4번 계단 오르는 방법, 2번계단에서 2칸 오르기 or 3번 계단에서 1칸 오르기

..

피보나치

 

 

 

class Main {

	static int m, n, answer;
	static int []dy;
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);

		n = in.nextInt();
		dy = new int[n+1];
		
		dy[1]=1;
		dy[2]=2;
		for (int i =3 ; i <= n; i++) {
			dy[i] =dy[i-2]+dy[i-1];
		}
		
		System.out.println(dy[n]);

	}

}

ex)
input
7
output
21