[Ch.10 - DP] 02. 돌다리 건너기

1. 계단오르기

 

설명

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.

그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

입력

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

출력

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

예시 입력 1 

7

예시 출력 1

21

---

돌다리를 건너야 하므로 dy[n+1]을 반환해야 한다.

dy = new int[n+2];
return dy[n+1];

---

package dynamic.ch10;

import java.util.Scanner;
//돌다리 건너기
//한칸 혹은 두칸씩 마지막에 도달
public class Dynamic02 {
	static int[] dy;
	static int solution(int n) {
		dy[1]=1;
		dy[2]=2;
		for(int i=3;i<=n+1;i++) dy[i]=dy[i-1]+dy[i-2];
		return dy[n+1];
	}
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		dy=new int[n+2];
		System.out.println(solution(n));
	}
}