Programmers Level 3: 멀리 뛰기

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

코딩테스트 연습 - 멀리 뛰기

풀이법

1) DP를 활용하면 쉽게 풀 수 있는 문제이다. (queue를 활용하여 풀 수 있으나 시간 초과에 유의해야 한다.)

2) 개인적으로 kakao 프로그래머스 level2 문제보다 쉽다고 생각했기에, 오래 걸리지 않고 문제를 풀 수 있었다.

arr[1]=1

arr[2]=2

arr[3]=3

arr[4]=5

arr[5]=8

등의 규칙이 존재했기에 점화식을 arr[i]=arr[i-1]+arr[i-2]로 세울 수 있었다.

수가 커지게 되면, overflow가 발생할 수 있으므로 long long type을 사용하면 쉽게 해결 가능하다

#include <string>
#include <vector>
#include <queue>
using namespace std;

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

/*
long long solution(int n) {
    long long answer = 0;
    queue<int> q;
    q.push(0);
    n=6;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        if(now==n)
        {
            answer++;
            continue;
        }
        if(now+1<=n)
            q.push(now+1);
        if(now+2<=n)
            q.push(now+2);
    }
    return answer%1234567;
}*/