계단을 오르는 경우의 수를 구하기

문제 url: https://leetcode.com/problems/climbing-stairs/description/

 

설명: 계단을 오르는데, 가장 맨 위 계단까지 n번의 경우의 수가 걸린다.

매번 1계단 또는 2계단을 오를 수 있다. n개의 계단이 주어질 때,

n개의 계단을 오르는 경우의 수를 구하는 로직을 작성하기

 

이 알고리즘을 작성하면서 알게된 개념

- 피보나치 수열: 앞의 두 수를 더한 값이 그 다음 나열되는 수라는 규칙을 갖는다.

그 다음 나열되는 수를 n이라고 했을 때, n의 값은 (n-2)+(n-1) 를 합한 값.

배열이 기준이 된다면 n-2, n-1는 배열의 인덱스 참조,

변수가 기준이 된다면 변수에 담긴 값을 참조한다고 생각하면 될 듯?

- dp(Dynamic Programming, 동적 계획법): 문제를 분할하고(문제를 작은 부분으로 나누고),

그 결과를 재활용하여(작은 문제의 결과 값을 저장하고, 같은 계산을 반복하지 않도록 함)

전체 문제를 해결하는 방법을 의미한다. 

- Bottom-Up 방식(dp를 구현하는 방식중 하나): 반복문과 배열(또는 변수들)을 활용하여

작은 문제부터 차례차례 해결해 나가는 방법을 의미한다.

 

실습

매번 계단을 1계단 또는 2계단을 올라갈 수 있을 때,

n개의 계단을 오를 수 있는 경우의 수를 구하는 기능을 갖는 클래스를 작성하기

 

클래스명 작명: 계단을 오르는 방법(경우의 수)의 갯수를 구하는 기능을 가진 클래스여서

'구한다', '계단 오르기', '방법의 수'에 핵심을 두었고, 구한다가 계산을 하는 의미로 판단하여

calculator, counter 가 클래스명에 들어가도 무방하다고 판단,

StairClimbCounter로 작명했다.

 

public class StairClimbCounter {


	// int stairs 계단의 갯수를 파라미터로 받고, 
    // 해당 계단의 갯수를 오르는 경우의 수를 반환하는 메서드명 countWays 라 명명
	public int countWays(int stairs) {
    	if(stairs<=0) return -1; // 계단의 갯수가 0이하에 해당하면(0또는 음수) -1을 반환한다.
        if(stairs<=2) return stairs; // 계단의 갯수인 n이 2이하에 해당하면 해당 n을 반환한다.
        
        int twoStepBefore=1;
        int oneStepBefore=2;
        int ways=0;
        
        // 위 조건으로 인해 계단의 시작 갯수는 3부터 시작
        // dp를 구현하는 방식중 bottom-up 방식을 사용,
        // 반복문과 변수들을 사용하여 피보나치 수열을 표현
        for(int current=3; current <= stairs; current++) {
        	ways=oneStepBefore+twoStepBefore;
            twoStepBefore=oneStepBefore;
            oneStepBefore=ways;
        }
        return ways;
    }
}