[Programmers] [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 이하인 정수입니다.
입출력 예
n	result
4	5
3	3

<입출력 예 설명>
- 입출력 예 #1
위에서 설명한 내용과 같습니다.

- 입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

---

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {

    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    long long prev_prev = 1; 
    long long prev = 2;      
    long long answer = 0; 

    for (int i = 3; i <= n; ++i) {
        answer = (prev_prev + prev) % 1234567;

        prev_prev = prev;  
        prev = answer;    
    }

    return answer; 
}

 

효진이가 1칸을 움직인다면 = 방법 1개

효진이가 2칸을 움직인다면 = 방법 2개

효진이가 3칸을 움직인다면 = 방법 3개

효진이가 4칸을 움직인다면 = 방법 5개

 

어... 이거 피보나치 비슷한거 맞나...?! 라는 생각이 들어 피보나치 해결법으로 풀었다.

 

---

 

<문제 설명>
피보나치 수는 F(0) = 0, F(1) = 1일 때,
1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

<예를 들어>

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수,
solution을 완성해 주세요.

<제한 사항>
n은 2 이상 100,000 이하인 자연수입니다.

<입출력 예>
n	return
3	2
5	5

- 입출력 예 설명
피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

---

#include <string>
#include <vector>

using namespace std;

int solution(int n) {

    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    int prev_prev = 0; 
    int prev = 1;      
    int answer = 0;   

    for (int i = 2; i <= n; ++i) {
        answer = (prev_prev + prev) % 1234567;

        prev_prev = prev;
        prev = answer;
    }

    return answer;
}

 

같은 이유로 위 코드에서 적절히 수정하면(시작값, 시작 위치) 동일하게 풀린다.

피보나치는 재귀함수로 풀 수 있지만 크기가 너무 커지면 스택오버플로우 현상이 일어나므로 주의해야한다

 

따라서 계속해서 %1234567 연산을 하는 이유는, 나머지 값이 항상 0 부터 1234566 사이의 범위로 유지되므로 오버플로우 현상을 방지할 수 있다

 

그런데

    if (n == 0) {

        return 0;

    }
여기서 return을 1로 해도 문제가 풀렸다. 왜지..ㅎㅎ