✍️Today I Learned

프로그래머스 - 멀리 뛰기

---

문제 설명

프로그래머스 문제 링크
한 번에 1칸이나 2칸을 뛸 수 있을 때 n칸을 건너갈 경우의 수를 구하고 이것을 1234567로 나눈 나머지를 리턴하는 함수 solution을 완성해라

제한사항

• 1 ≤ n ≤ 2000

---

실패한 풀이

1칸, 2칸을 뛸 수 있고 이들의 경우의 수를 구하는 문제라 중복 조합을 푸는 문제라고 생각했다.

n이 68이상이면 NumsOfCases(i, j)가 오버플로우로 값이 바뀌어 실패한다.

using namespace std;

// (i + j)! / i! * j!
// (i + j)*...*(i+1) / j!
long long NumsOfCases(int a, int b)
{
    long long result = 1;
    for(int i=1; i<=b; i++)
    {
        result *= (a + i);
        result /= i;        
    }
    return result;
}
long long solution(int n) {
    long long answer = 0;
    for(int i=0; i<=n/2; i++)
    {   
        // i: 2의 개수
        // j: 1의 개수
        int j = n - 2 * i;
        // (i + j)! / i! * j!
        answer = (answer + NumsOfCases(i, j)) % 1234567;
    }
    return answer % 1234567;
}

최종 풀이

피보나치 수열 방식
계단오르기 문제와 동일한 구조이다.
n개의 계단을 오르는 경우의 수는 n-1에서 1칸 오르거나 n-2에서 2칸을 오르는 방법밖에 없기 때문에 n-1개의 계단을 오르는 경우의 수 + n-2개의 계단을 오르는 경우의 수 와 같다.

using namespace std;

long long solution(int n) {
    if(n<2) return 1;
    int a=1;
    int b=1;
    for(int i=2; i<=n; i++)
    {   
        int temp = (a+b) % 1234567;
        a=b;
        b=temp;
    }
    return b;
}

도저히 오버플로우가 안 잡혀서 힌트보고 진행했다. 피보나치 수열을 사용하라는 힌트를 보니까 그제야 문제에서 그 부분이 보였다.
문제를 너무 곧이 곧대로 보고 방법을 써내려가지말고 좀 더 간단한 방식이 있는지 생각해 봐야겠다.