02. 돌다리 건너기

 

설명

다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요?

 

 

 

예시

7

 

34

 

 

 

 

풀이

피보나치와 마찬가지다.

 

하지만 역시 1 2 3 5 8 ..이런식으로 증가하는 규칙을 찾아내 dp로 풀수 있어야한다.

 

또한 7이 끝이아니고 돌다리가 7개니까 8번째 arr[8]이 답이 된다.

import java.util.*;



class Main {
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n= sc.nextInt();
		
		int [] arr = new int[n+2];
		
		arr[1]=1;
		arr[2]=2;
		
		for(int i=3; i<=n+1;i++) {
			arr[i]= arr[i-2]+arr[i-1];
		}
		System.out.println(arr[n+1]);

	}

	
}