[Algorithm]알고리즘 자바_72 계단 오르기 :: DynamicProgramming

 

💬 문제 설명

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다.

만약 총 4계단을 오른다면 그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.

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

 

🔨 입출력 예

입력 

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

7

 

출력

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

21

 

 

​

💻 Solution.java

• 동적 계획법은 큰 문제를 작은 문제로 분할해서 푸는 것
• 이 문제에는 피보나치를 적용시킨다
• 가장 작은 문제인 1번째 계단은 1가지의 방법, 2번째 계단은 2가지의 방법을 갖고 있다

/* 계단 오르기 :: 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; i++) {
			dy[i] = dy[i - 2] + dy[i - 1];
		}
		return dy[n];
			
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();		
		dy = new int[n + 1];
		
		System.out.println(main.solution(n));
		
		sc.close();
		return ;
	}
}