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

[level 2] 멀리 뛰기 - 12914

문제 링크

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.

---

성능 요약

메모리: 4.14 MB, 시간: 0.02 ms

채점결과

정확성: 100.0
합계: 100.0 / 100.0

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

대충 순열조합 문제 같은데 잘 생각이 안나서 그냥 노가다로 경우의 수 생각해봤다.

f(4) = 5

f(5) = 8

f(6) = 13

f(7) = 21

.

.

.

쓰다보니 뭔가 어디서 많이 본 수열...

피보나치 수열로 냅다 풀었더니 풀렸다.

 

사실 원래는 fib 배열 완성한 후에 answer 에 넣을 때 1234567로 나눠줬었는데, 그렇게 하니까 숫자 범위가 long long 도 넘어가서, 그냥 바로 나머지 넣어줬다.

 

 

그리고 왜 피보나치 수열인지 찾아보니...

효진이가 n번째 칸에 도달하는 방법은 n-1번째 칸에서 1칸을 뛰거나, 
n-2번째 칸에서 2칸을 뛰는 방법으로 나눌 수 있습니다. 이것은 피보나치 수열의 정의와 일치합니다.

챗GPT최고

 

n-1에서 1칸을 뛰는 경우의 수 = f(n-1)

n-2에서 2칸을 뛰는 경우의 수 = f(n-2)

 

이 생각만 빠르게 할 수 있으면 금방 풀리는 문제인 것 같다.

나는 수학 머리가 안되나...

 

*** 피보나치 수열은 fib[0] 이 1이지만, 이 문제에서 n=0일 때는 0이 맞는 것 같아서 0으로 넣어줬다. 물론 n은 1보다 크다는 조건이 있긴 했지만...

 

다른 문제 풀이를 보니 신기하게 푼 문제들도 많았는데, 문제가 개편된 이후로 정답이 하나도 안맞게 나와서 그냥 이해 안하기로 했다.