백준 1788번 [피보나치 수의 확장](C++) -yes6686- 티스토리

백준 문제 풀이: 1788 [피보나치 수의 확장]

---

문제 링크: https://www.acmicpc.net/problem/1788

문제 설명:

피보나치 수열은 다음과 같은 점화식으로 정의됩니다:

• F(0) = 0, F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)
• F(n) = F(n+2) - F(n+1) (n < 0)

이 문제에서는 정수 n에 대해 F(n)을 구하고, 다음을 출력해야 합니다:

1. F(n)이 양수, 음수, 또는 0인지에 따라 각각 1, -1, 또는 0
2. F(n)을 10억(1,000,000,000)으로 나눈 나머지

---

문제 해결 코드

#include <iostream>
#include <cmath>
#define MOD 1000000000
using namespace std;

int dp[1000001]; // F(n)을 저장하기 위한 배열

int main() {
    int n;
    cin >> n;

    // 초기값 설정
    dp[0] = 0;
    dp[1] = 1;

    // 절댓값 n까지 피보나치 수 계산
    for (int i = 2; i <= abs(n); i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }

    // F(n)의 부호 출력
    if (n == 0) {
        cout << 0 << '\n'; // F(0) = 0
    } else if (n < 0) {
        cout << (n % 2 == 0 ? -1 : 1) << '\n'; // F(-n)의 부호 결정
    } else {
        cout << 1 << '\n'; // F(n)이 양수일 경우
    }

    // F(n)의 값 출력
    cout << dp[abs(n)] << '\n';

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 F(n)을 구합니다. 음수 입력에 대해 피보나치 수의 성질을 활용하여 결과를 처리합니다.
• 구현 세부사항:
  • 배열 dp는 0부터 |n|까지의 피보나치 수를 저장합니다.
  • n < 0일 때, 짝수 인덱스에서 F(n)이 음수가 되는 성질을 활용합니다.
  • 출력은 F(n)의 부호와 값을 각각 출력합니다.
• 시간 복잡도 분석: O(|n|), 여기서 |n|은 입력 값 n의 절댓값입니다. 각 단계에서 상수 시간 연산이 이루어집니다.

---

결과

F(n)의 부호와 10억으로 나눈 나머지가 정확히 출력됩니다. 동적 프로그래밍을 사용하여 효율적으로 해결할 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!