백준 8394번 [악수](C++) -yes6686- 티스토리

백준 문제 풀이: 8394번 [악수]

---

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

문제 설명:

N명이 원탁에 앉아 서로 악수를 할 때, 마지막 사람이 악수를 하지 않더라도 나올 수 있는 악수의 총 경우의 수를 계산하는 문제입니다. 이 문제는 피보나치 수열의 점화식을 기반으로 풀 수 있습니다. 결과는 마지막 자리 숫자만 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n == 1 || n == 2 || n == 3) {
        cout << n << '\n'; // 초기에 N이 작은 경우 직접 출력
    } else {
        int a = 1; // F(1)
        int b = 2; // F(2)
        int c = 3; // F(3)
        for (int i = 3; i <= n; i++) {
            c = (a + b) % 10; // 마지막 자리만 계산
            a = b; // 다음 피보나치 수 계산을 위해 이동
            b = c;
        }
        cout << c << '\n'; // 결과 출력
    }
}

---

코드 설명

위 코드는 피보나치 점화식을 사용하여 마지막 자리 숫자를 계산합니다. 주요 로직은 다음과 같습니다:

1. 기본 조건 처리: N이 1, 2, 3인 경우 결과를 바로 출력합니다.
2. 피보나치 점화식: F(N) = F(N-1) + F(N-2)를 기반으로 반복문을 통해 마지막 자리 숫자를 계산합니다.
3. 모듈러 연산: 마지막 자리만 필요하므로 연산 과정에서 10으로 나눈 나머지를 저장하여 계산을 최적화합니다.

시간 복잡도:

• O(N): N까지의 피보나치 수를 계산하는 반복문을 사용합니다.

---

결과

위 코드는 입력된 N에 대해 피보나치 점화식을 사용하여 마지막 자리 숫자를 정확히 출력합니다. 더 효율적인 구현 방식이나 추가적인 제안을 댓글로 공유 부탁드립니다!