[Algorithm] 계단을 오르는 방법

계단을 오르는 방법

김토스가 N개의 계단을 오르려고 합니다. 김토스는 한번에 1~3개의 계단을 이동할 수 있습니다.

N개의 계단을 올라가는 방법이 총 몇 가지가 있는지 계산하는 함수를 구현해주세요.

입력 예시

solution(numOfStairs) 함수의 인자는 아래와 같이 전달됩니다.

• 계단의 수 N : numOfStairs (1 <= N <= 70)

출력 예시

주어진 계단의 수 N(numOfStairs)로부터, 계단을 오를 수 있는 방법의 수를 반환합니다.

예시

• 계단이 1개라면, 오를 수 있는 방법은 한 번에 1계단을 올라서 총 1가지이다.
  • [1]
• 계단이 2개라면, 오를 수 있는 방법은 한 번에 1계단씩 2번 오르거나, 한 번에 2계단을 올라서 총 2가지이다.
  • [1, 1], [2]
• 계단이 3개라면, 오를 수 있는 방법은 총 4가지이다.
  • [1, 1, 1], [1, 2], [2, 1], [3]
• 계단이 4개라면, 오를 수 있는 방법은 총 7가지이다.
  • [1, 1, 1, 1], [1, 2, 1], [2, 1, 1], [1, 1, 2], [2, 2], [1, 3], [3, 1]

풀이

위의 예시에 나온 것부터 각 계단마다 오를 수 있는 경우의 수를 우선 정리해봅니다.
개인적으로 그냥 문제를 보는 것보다 노트에 푸는 방법을 간단하게 정리하고 푸는게 도움이 되는 것 같습니다.

계단 1 -> 경우의 수 1

계단 2 -> 경우의 수 2

계단 3 -> 경우의 수 4

계단 4 -> 경우의 수 7

계단 5 -> 경우의 수 13

계단 6 -> 경우의 수 24

이렇게 올라갈 수 있는 경우의 수를 나열해보니 규칙이 보이네요~
앞선 3개의 경우의 수를 합친 값이 해당 계단을 올라갈 수 있는 경우의 수인 피보나치 수열로 되어 있는 것을 알 수 있습니다.
이제 규칙을 알았으니 문제를 풀도록 하겠습니다~

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ClimbStairs {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int first, second, third, temp;
        if(N==1){
            System.out.println(1);
            return;
        } else if(N==2){
            System.out.println(2);
            return;
        } else if(N==3){
            System.out.println(4);
            return;
        } else {
            first = 1;
            second = 2;
            third = 4;
            for(int i=0;i<N-3;i++){
                temp = first;
                first = second;
                second = third;
                third += temp+first;
            }
            System.out.println(third);
            return;
        }
    }
}