[Algorithm]알고리즘 자바_73 돌다리 건너기 :: DynamicProgramming

 

💬 문제 설명

철수는 학교에 가는데 개울을 만났습니다.

개울은 N개의 돌로 다리를 만들어 놓았습니다.
철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.

철수가 개울을 건너는 방법은 몇 가지일까요?

 

🔨 입출력 예

입력 

• 첫째 줄은 돌의 개수인 자연수 N(3≤N≤35)이 주어집니다.

7

 

출력

• 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.

34

 

 

​

💻 Solution.java

• 이전 문제 '계단 오르기'와 유사
• 개울의 시작과 끝을 0, n + 1로 추가하자
• 리턴 받아야 하는 값은 dy[n + 1]

/* 돌다리 건너기 :: Dynamic Programming */
import java.util.*;

public class Main {
	static int [] dy;

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