[백준] 1003번

이 문제는 이미 해결한 문제를 table 느낌으로 저장만 한다면 손쉽게 해결 가능한 문제이다.

 

 

자 find 부분에서 등호처리에서 2번이나 틀렸다. 분명히 계산 안한 부분인데, 같은 거를 물어보면 바로 return 되서 분명히 문제가 발생한 듯하다. 다음부터는 더욱더 알고리즘을 이해야하겠다.

#include <map>
#include <iostream>
#include <sstream>

typedef struct zo {
    int zPart;
    int oPart;
} zo;

class fiboCount {
private:
    std::map<int, zo> table;
    int index = 0;
public:
    void init() {
        table[0].zPart = 1;
        table[0].oPart = 0;
        table[1].zPart = 0;
        table[1].oPart = 1;
        index = 2;
    }
    void insert(const int locate) {
        while (locate >= index) {
            table[index].zPart = table[index-2].zPart + table[index-1].zPart;
            table[index].oPart = table[index-2].oPart + table[index-1].oPart;
            index++;
        }
    }

    zo find(int f) {
        if (f >= index) {
            insert(f);
            // 이 경우에는 insert를 재귀적으로 해서 발견
        }
        return table[f];
    }

};

int main() {
    std::ostringstream buffer;
    int t, n;
    std::cin >> t;
    fiboCount fc;
    fc.init();
    for (int i = 0; i < t; i++) {
        std::cin >> n;
        zo temp = fc.find(n);
        buffer << temp.zPart << " " << temp.oPart << std::endl;
    }
    std::cout << buffer.str();
    return 0;
}