[백준] 1788번 피보나치 수의 확장

문제: 1788번: 피보나치 수의 확장

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
//#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    vector<int> plusNums(1000001); // 0~1000000
    vector<int> minusNums(1000001); // -1000000 ~ 0

    plusNums[1] = 1;
    minusNums[1] = 1;
    for (int i = 2; i < 1000001; i++) {
        plusNums[i] = (plusNums[i - 1] + plusNums[i - 2]) % 1000000000;
        minusNums[i] = (minusNums[i - 2] - minusNums[i - 1]) % 1000000000;
    }
    int n;
    cin >> n;
    
    int answer;
    answer = n < 0 ? minusNums[n * -1] : plusNums[n];

    if (answer == 0) {
        cout << 0 << "\n" << answer;
    }
    else if (answer > 0) {
        cout << 1 << "\n" << answer;
    }
    else {
        cout << -1 << "\n" << -1 * answer;
    }

    return 0;
}

 

나는 n 이 음수인 경우와 아닌 경우를 따로 배열로 만들었다.

 

n 이 양수인 경우의 table 은 기존 피보나치 수열을 구하는 방식과 똑같이 해주면 된다. n 이 음수인 경우의 table 은 기존 피보나치 수열 계산 방법과 살짝 다르다. n 이 음수인 경우의 dp[i] 의 값은 dp[i-2] - dp[i-1] 과 같다.

 

처음 제출했을 때 틀렸습니다가 떠서 문제를 다시 읽어봤더니 " 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다." 라고 되어있었다. 즉, dp 에 수를 저장할 때 1,000,000,000 으로 나눈 나머지값을 저장해야 하는 것이었다;;

 

왜 문제를 제대로 안 읽을까? 아니 사실 읽긴 했는데 문제 푸느라 급급해서 문제 조건을 쉽게 까먹는 것 같다;; 조심해야 하는데 바뀌지를 않는다;;