[프로그래머스] 멀리 뛰기

1. 문제

 

1234567로 나눈 나머지를 리턴하라는 부분이 있다면 오버플로우가 발생할 가능성이 있다는 의미인 것 같다. 실제로 이 문제를 조합을 활용해서 풀었는데 오버플로우로 인해 문제를 해결할 수 없었다. 다른 방법을 찾아봤고 사람들은 피보나치 수열을 활용하여 풀었다고 한다.. 어떻게 이 문제를 보고 피보나치를 떠올릴 수 있었을까 ..

---

2. 조합 코드

long long solution(int n) {
    long long answer = 0;
    
    int m = n/2;
    
    int left = 0;
    int right = n;
    
        
    do{
        long comb = 1;  // 조합 값 저장
        
        for (int i = 0; i < left; ++i) {
            comb = comb * (right - i) / (i + 1);  // 조합 공식 적용
        }
        
        answer += comb;
        --right;
        ++left;
    }while(right >= left);
    
    answer %= 1234567;
    
    return answer;
}

시간 복잡도를 고려해서 팩토리얼을 반환하는 함수도 작성하지 않고, for문 1개로 조합을 구현했다. 하지만 입력이 2000으로 주어지는 경우에는 comb의 값이 어마어마하게 커질 것이다. 최종 연산 이후 answer를 1234567로 나눠주는 과정에서 이미 answer에는 comb의 오버플로우가 반영된 값을 더한 결과값이 저장되어 있을 것이다. 실제로 코드 제출 후 6번까지는 깔끔하게 통과했지만, 7번 이후로는 오버플로우가 발생해 다른 방법을 찾을 수밖에 없었다.

---

3. 개선된 코드

long long solution(int n) {
    vector<long long> dp(n + 1);
    dp[0] = 1;  // n=0일 때 경우의 수 (의미 없는 값)
    dp[1] = 1;  // n=1일 때 1가지

    for (int i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }

    return dp[n];
}

이게 피보나치 수열 알고리듬을 활용한 코드이다. 이 문제가 왜 피보나치 수열과 관련이 있는지부터 알아야 한다.

n = 1인 경우 결과 값은 1

n = 2인 경우 결과 값은 2

n = 3인 경우 결과 값은 3

n = 4인 경우 결과 값은 5

n = 5인 경우 결과 값은 8이다.

패턴을 보면 n = (n-1) + (n-2) 인 것을 확인할 수 있다. 문제에서도 테스트 케이스의 값을 n = 4인 경우와 n = 5인 경우를 순차적으로 알려준 것을 보니 간접적인 힌트였나보다. 다른 문제에서도 n = 4 일 때 5, n = 5일 때 8인 상황이 있다면 피보나치 수열의 알고리듬을 의심해봐야겠다.