[BOJ 8394, C++] 악수

https://www.acmicpc.net/problem/8394

8394번: 악수

 

 

1. 문제 증명

---

예시가 4만 나와있는데, n = 1 ~ 3일 때도 확인해보면 피보나치 수열의 점화식이 나옵니다.

arr[i] = arr[i-1] + arr[i-2]

 

피보나치 수열 점화식을 증명하는 방법은 생각보다 간단합니다.

회의에 참석한 사람 N명이 있고, 이미 우리가 1명부터 N-1명일 때까지의 경우의 수를 모두 구했다고 가정해보겠습니다.

이때 N-1명일 때의 경우의 수는 dp[N-1]입니다.

 

N번째 사람이 추가되면 경우의 수가 2가지로 나뉘게 됩니다.

 

1) N번째 사람이 악수를 하지 않는 경우

이 경우엔 1번째 사람 ~ N-1번째 사람이 악수한 경우의 수를 구하면 되므로 dp[N-1]이 됩니다.

 

2) N번째 사람이 악수를 한 경우

N번째 사람이 악수를 하는 경우는 N-1번째 사람과 무조건 악수를 하는 경우뿐입니다.

그래서 N-1번째 사람과 N번째 사람은 악수를 하는 것이 확정되었으므로 dp[N-2]를 구하면 됩니다.

 

증명 내용 자체는 수학적 귀납법까지 사용해야 완벽하지만, 문제 푸는데 그정도는 필요한 내용이 아니라서 생략하겠습니다.

 

그래서 결국에는 dp[N] = dp[N-1] + dp[N-2]가 나오게 됩니다.

보통 이런 문제를 보면 예시를 구해보고, 규칙성을 찾아 바로 코드로 짜서 제출했는데, 생각해보니 그동안 따로 피보나치 수열 점화식에 대한 증명을 해보지 않았어서 한 번 해봤네요.

---

 

2. 코드

---

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N = 10000002;
 
ll dp[N] = { 0 };
 
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, -1, sizeof(dp));
 
    int n;
    cin >> n;
 
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10;
    }
    
    cout << dp[n];
 
    return 0;
}

---