8659.GCD c++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW1l1s2KWn4DFARC 

SW Expert Academy

- 규칙찾기 (정답)

a2 = a1+b1 / b2= a1;

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

int main() {

    int test_case;
    int T;
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case) {
        int k;
        cin >> k;

        long long map[100][2];
        pair<long long, long long> result;
        
        map[0][0] = 2;
        map[0][1] = 1;
        for (int i = 1; i < k; i++) {
            map[i][0] = map[i-1][0] + map[i-1][1];
            map[i][1] = map[i - 1][0];
        }
        
        result.first = map[k - 1][0];
        result.second = map[k - 1][1];

        cout << "#" << test_case << " " << result.first << " " << result.second << endl;
    }

    return 0;
}

 

- 완전탐색 구현하면 시간복잡도 큼.. (디버깅에러)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
//#include <fstream>

using namespace std;

pair<int, int>result;
int flag;
int k;

void check(int startNum, int changeNum) {

    if (changeNum <= 0) {
        return;
    }

    int a = startNum;
    int b = changeNum;
    for (int i = 0; i < k; i++) {
        
        int temp = a % b;
        if (temp == 0) {
            if (i == k - 1) {
                flag = 0;
                result.first = startNum;
                result.second = changeNum;
                return;
            }
            break;
        }
        else if(temp!=0){
            a = b;
            b = temp;
        }
    }

    check(startNum, changeNum -= 1);

}

int main() {

    int test_case;
    int T;
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case) {
        
        cin >> k;

        int Num = 1;
        flag = 1;
        while (flag) {
            check(Num +=1, Num - 1);
        }

        cout << "#" << test_case << " " << result.first <<" "<<result.second << endl;
    }

    return 0;
}