[코딩테스트C++]멀리 뛰기

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/12914?language=cpp

멀리 뛰기

나의 풀이

#include <string>
#include <vector>
#define DIV 1234567

using namespace std;

long long solution(int n) {
    long long answer = 0;
    vector<int> dp(n, 0);
    if(n == 1)
        return 1;
    dp[0] = 1;
    dp[1] = 2;
    for(int i=2;i<n;i++){
        dp[i] = (dp[i-2] + dp[i-1])%DIV;
    }
    return dp[n-1]%DIV;
}

모범 답안

#include<iostream>
#include<vector>
using namespace std;

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

배울 점

• 그냥 정석대로 DP로 풀었는데 규칙은 피보나치로, 변수 두개로 풀 수 있다.

#include <string>
#include <vector>
#define DIV 1234567

using namespace std;

long long solution(int n) {
    long long answer = 0;
    int num[] = {1, 2};
    if(n == 1)
        return 1;
    for(int i=2;i<n;i++){
        int n = (num[0] + num[1])%DIV;
        num[0] = num[1];
        num[1] = n;
    }
    return num[1];
}

• 근데 저사람은 진짜ㅋㅋㅋㅋ 코드 한줄풀이 리스펙
• 맞다 피보나치는 재귀로 풀 수 있다. 2보다 작을 경우 1을 반환하고 아니면 두 차례 전의것과 한 차례 전의 것의 반환값을 더해 반환. 재귀의 매직