[Leetcode] 70. Climbing Stairs

Identifying the Problem

계단을 한번에 1칸 혹은 2칸 오를 수 있을 때,

계단을 n 만큼 오를 수 있는 가능한 경우의 수를 구한다.

Organizing thoughts

가장 먼저 조합으로 풀릴 수 있을 거라 생각했고,

그렇게 해서 풀었지만, 가능한 펙토리얼의 한계가 있었고,

그걸 해결하려 식을 최대한 간소화 하는 작업도 했지만 double이 나타나는 값의 한계가 있었다.

따라서 정답을 참고해본 결과 경우의 수는 피보나치 수열을 따랐다.

Sourcecode

1. 펙토리얼의 규칙성을 찾아서 작성한 코드이다.

간단히 설명하면

n!/(x!y!) 이라고 했을 때 이 값을 sum에 누적 시킨다.

n은 매 차수마다 1씩 줄어들고,

x는 1을 n개 만큼 더한 변수이고, x의 초기값은 n과 같고 2씩 줄어든다.

y는 2의 개수이고, 초기 0부터 시작해 1씩 증가한다.

이 과정을 x가 0보다 작아질 때 까지 하면 된다.

int climbStairs(int n)
{
  /*int y = n;
  int z = 0;
  int sum = 0;
  
  int big;
  int small;
    
  if(n == 1) return 1;
    
  while(y>-1)
  {
      big = y; small = z;
      if(z>y){big = z; small = y;}
      
      sum +=multi(n,big,small);
      
      n = n - 1;
      y = y - 2;
      z = z + 1;
      
  }
  
      return sum;
}


int multi(int u,int b,int s)
{
  double ans = 1;
  
  while(u>b)
  {
   ans = ans*u/s;
   
   u--;
   s--;
  }

  return ans;
}

 

2. 피보나치 수열을 n까지 구한 값이다.

피보나치 수열을 간단히 설명하면

A[1] = 1

A[2] = 1 일 때,

n>2 이면 A[n] = A[n-2] + A[n-1] 을 만족하는 수열이다.

 

1. n<4 인경우는 n과 a[n] 값이 같아 그대로 리턴하고

2. 나머지는 피보나치 수열의 성질을 따라 작성한다.

 

int climbStairs(int n)
{

  int sum = 0;
    
   if(n<4) return n; //1
   int a = 1;
   int b = 2;
   int i = 3;
    
   while(i<=n) //2
   {
    sum = a+b;
    a = b;
    b = sum;

    i++;
   }



    return sum;
}

Mistake

언젠가는 100! 구하는 코드도 짜보자. 분하다.

New things learned

단순하게도 생각해보자.