|C++| 백준 1904 - 01타일(피보나치, 조합)

0. [c++] 백준

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

1. 풀이

이 문제는 3가지 방법을 활용해서 문제를 풀이 할 수 있었다.

1) 조합을 활용한 방법

입력으로 N이 주어질 때, 우리가 구해야 할 값은 조합을 활용해서 풀 수 있는데

결과 값은 과 같이 구할 수 있다.

하지만, 이를 활용해서 문제를 푸니 N이 10,000 정도에서 시간제한을 넘기지 못했다.

2) 조합을 필요한 부분만 활용하는 방법

1번과 같이 문제를 해결해보니 조합에서 윗부분과 아랫부분으로 나뉘어지게 되는데, 윗부분의 맨 앞 숫자를 지워주고, 맨 뒤에 숫자 2개를 추가해준다.

아랫부분은 계속 1자리씩 추가해주면, 각 차례에 원하는 nCi를 구할 수 있었다.

하지만, 이와 같은 구현도 실패하였는데, unsigned long long을 초과해버려서 원하는 수를 구할 수 없게 되었다.

3) 피보나치 수를 이용하는 방법

이 문제는 특이하게도 피보나치 수를 만족하면서 숫자가 배열되는 특징이 있었다.

이러한 특징을 활용하여 문제를 해결하면 끝!

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include<iostream> #include<algorithm>   using namespace std;   typedef unsigned long long ull;   const int INF = 15746;   //int calc(const int& N) { //    int ret = 1; //    int MAX = N - 2; //    ull next = 0; //    if (N >= 3) { //        next = N - 1; //        ret = (ret + next) % INF; //    } //    else if(N == 2) { //        return 2; //    } //    else { //        return 1; //    } //     //    for (int i = 2; i <= N/2; i++) { //        next /= (N - i + 1); //        next *= MAX--; //        next *= MAX--; //        next /= i; //        ret = (ret + next) % INF; //    } //    return ret; //}   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);          int N;     cin >> N;     if (N == 1)         cout << 1;     else if (N == 2)         cout << 2;     else {         int a, b, temp;         a = 1;         b = 2;         for (int i = 3; i <= N; i++) {             temp = a;             a = b;             b = (a + temp) % INF;         }         cout << b;     }            return 0; } Colored by Color Scripter

cs

주석으로 처리된 부분은 2번 풀이를 코드로 구현한 것이다.

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!