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

문제는 다음과 같습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

풀이 코드는 다음과 같습니다.

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;
    long arr[2001];
    arr[0]=0;
    arr[1]=1;
    arr[2]=2;
    for(int i{3};i<2001;i++)
    {
        arr[i]=(arr[i-1]+arr[i-2])%1234567;
    }
    answer=arr[n];
    return answer;
}

전형적인 피보나치수열 문제입니다.

그 이유는 맨 마지막 n번째 계단을 오르기 위해서는 경우의 수가 2개 존재하는데 그 경우가

n-2번째 계단에서 올라오는 방법과 n-1번째 계단에서 올라오는 방법이기 때문입니다. (계단은 1칸 또는 2칸만 오를 수 있기 때문입니다.)

예시로, 3번째 칸에 올라가기 위해서는 1번째 칸에서 2칸을 오르는(1+1 또는 2) 방법과 2번째 칸에서 1칸을 오르는 방법만 존재하기 때문입니다.

그냥 이렇게 풀면 틀리게 되는데 그 이유는 

1234567을 나눈 나머지를 리턴해야하기 때문입니다.

이 부분을 읽지 않고 풀었다가 저 역시 계속 뜨는 오답에 "왜 틀린 거지?" 했습니다. 문제를 끝까지 읽어야 한다는 중요성을 다시 한번 보여준 것 같습니다.