프로그래머스 알고리즘 level3 멀리 뛰기

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.

수학적으로 생각해보았다.

항상 수학적인 깨달음은 그래프화를 하면서 나오기에, 일단 그래프를 그렸다.

위의 식에서 n은 칸의 개수, x는 한칸 움직이는 횟수, y는 두칸 움직이는 횟수다.

2x+y=n이라는 식에서

만약 n이 4이면 x, y는 위 그래프에서 x가 정수인경우의 정의역과 그에 따른 치역을 가진다.

n이 4 => x는 0, 1, 2

y는 4, 2, 0

그리고 각 순서쌍에 대하여 경우의 수를 구하는 식을 만들어내었다.

(n-x)!/{(n-2x)!x!}인데 경우의 수 문제에서 남학생과 여학생 문제를 기억하면 쉽다.

n-x는 총 학생의 수, n-2x는 남학생 수, x는 여학생 수 이렇게 생각하면 식이 나온다.

해당 식을 다른 방법으로 접근하여 점화식 형태로 바꿔서 계산을 해보려고 시도해보았으나 여간 쉽지않아서 위의 형태로 해결하였다.

코딩에서는 알고리즘을 

public static long factorial(long i)
{
if(i>1)
 return i * factorial(i-1);
else if(i==0)
  return 1;
else
  return i;
}
public static long factorial2(long i,long j)
{
if(j<i)
 return i * factorial2(i-1,j);
else
  return 1;
}
 long result=0;
    for(int i=0;i<=num/2;i++)
    {
      result += factorial2(num-i, num-2*i)/factorial(i);
    }
      return result;

위와같이 팩토리얼을 2개의 함수로 나누었다.

그 이유는 사람이라면 169!/167!을 계산할때 당연히 약분하여 169x168이라 순식간에 계산이 되지만 컴퓨터의 팩토리얼 정의를 위의 factorial 함수처럼 하면 169!/167!을 전부다 계산해서 오버플로 에러가 나버린다.

따라서 factorial2라는 함수를 선언하여 2개의 숫자를 입력받아서 약분을 해주는 함수를 넣어서 해결하였다.