#계단오르기

답을 직관적으로 알 수 있게 소형화하여 보텀업 방식으로 올라간다.

1번 계단으로 갈 수 있는 방법의 수는 1

2번 계단으로 갈 수 있는 방법의 수는 2

3번 계단으로 갈 수 있는 방법의 수는 1번에서 2계단 점프 or 2번에서 1계단 점프 1+2 = 3

 

1번 계단으로 갈 수 있는 방법에서 2계단 점프+2번 계단으로 갈 수 있는 방법에서 1계단 점프의 합

 

import java.util.*;
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 T = new Main();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        dy=new int[n+1];
        System.out.print(T.solution(n));
    }
}