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

문제

멀리 뛰기 : 문제 링크

문제 분석

• 효진이는 멀리 뛰기를 연습하고 있다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있다. 칸이 총 4개 있을 때,

(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)

• 효진이는 5가지 방법으로 맨 끝 칸에 도달할 수 있다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성. 예를 들어 4가 입력된다면, 5를 return

• 제한 사항

• n은 1 이상 2000 이하인 정수 이다.

• 해당 문제는 피보나치 수와 흡사한 규칙을 띄고 있다. 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 이고, 해당 문제는 n2 = 2, n3 = 3일 때, 4이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용된다.

• F(4) = F(2) + F(3) = 2 + 3 = 5
• F(5) = F(3) + F(4) = 3 + 5 = 8
• F(6) = F(4) + F(5) = 5 + 8 = 13

• 효진이가 끝에 도달하는 방법에서 1234567를 나눈 나머지를 저장할 long long형 변수 answer을 0으로, n이 2일때의 답인 2, 3일때의 답인 3을 정수형 변수 n2, n3에 각각 저장. if문을 사용하여 n이 3이하일 경우 n을 return 하고, 4이상의 경우 for loop를 통해 초기화식 i = 4부터 n까지 순환. answer에 n2와 n3을 더하고 1234567을 나눈 나머지를 저장하고, n2에 n3값을, n3에 answer을 저장하는 과정을 반복. loop 탈출 후, 최종적으로 저장된 answer을 return

풀이

using namespace std;

long long solution(int n) {
    long long answer = 0;
    int n2 = 2, n3 = 3;
    
    if(n <= 3) return n;
    for(int i = 4; i <= n; ++i) {
        answer = (n2 + n3) % 1234567;
        n2 = n3;
        n3 = answer;
    }
    return answer;
}