<Easy> Climbing Stairs (LeetCode : C#)

https://leetcode.com/problems/climbing-stairs/

📕 문제 설명

n칸의 계단에서 1칸이나 2칸씩 올라갈 수 있을 때 몇 가지 방법으로 꼭대기에 올라갈 수 있는지 반환

• Input
  n칸
• Output
  올라갈 수 있는 경우의 수

예제

풀이

1. 주어진 n칸에 대해 2로 나눠 2를 사용할 수 있는 개수를 구한다.
2. 2를 0 ~ 사용할 수 있는 개수에 대해서 조합을 계산한다. (nCr -> n = 현재 사용하는 1과 2의 개수, r = 2의 개수)

public class Solution {
    public int ClimbStairs(int n) {
        int twoCount = n / 2;
        int count = 0;
        long answer = 0;
        
        for (int i = 0; i <= twoCount; i++)
        {
            count = n - (i * 2) + i;
            answer += nCr(count, i);
        }

        return (int) answer;
        
    }

    public long nCr(int n, int r)
    {
        long value = 1;

        for (int i = 1; i <= r; i++)
        {
            value *= (n - (i - 1));
            value /= i;
        }

        return value;
    }
}

결과

(시간은 의미없어 보임)