[프로그래머스/C++]Lv.2 - 멀리 뛰기

문제 링크

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

시도한 방법

n개중에 m개를 고르는 방법을 구하는 함수를 만든 뒤 (1, n), (2, n-1)... (m,n-m)까지 구해서 모든값을 더하려고 했으나 나누기에서 맞아떨어지지 않아서 짤리는 경우도 생기고, double로 하자니 1234567의 나머지를 구할 수 없고, 다시 long long으로 형변환하기도 되지 않았다.

내 코드

다른 사람의 풀이

1.
#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long arr[2001];
    arr[0] = 1;
    arr[1] = 1;
    for(int i = 2; i <= n; i++)
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
    
    return arr[n];
}
2.
#include<iostream>
#include<vector>
using namespace std;

int jumpCase(int num)
{
    return num < 2 ? 1 : jumpCase(num - 2) + jumpCase(num - 1);
}
int main()
{
    int test = 4;

//아래는 테스트로 출력해 보기 위한 코드입니다.
    cout << jumpCase(test);
}

다른 사람의 풀이 해석

타일링 알고리즘을 사용하였다.
1.
i = (i-1) + (i-2) 인걸 사용하여 구하였다.
2.
재귀함수를 사용하였다. num이 2 이하일 경우 1, 그 외에는 num-2 + num-1을 재귀함수로 구현하였다.