작심 24/7

1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 순진하게 문제에 나와있는 대로 재귀를 해버리면 시간 초과 난다. 게다가 테스트 케이스 만큼 값을 여러 번 출력해야 하기 때문에 메모이제이션으로 풀어준다. N을 입력 받기 전에 미리 벡터에 0이 출력되는 횟수와 1이 출력되는 횟수를 저장시켜놓고 N을 받으면 거기서 바로 꺼내와 출력시키도록 하면 된다. #include #include using namespace std; int zero = 0, one = 0; vector fibonacci; int main() { fibonacci.push_back(pair(1, 0)); fibonacci.pu..

4150번: 피보나치 수 문제 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 www.acmicpc.net 정답이 1000자리 이하라는 말을 보고 눈을 의심했었다. int나 long long으로는 절대 풀 수 없기 때문에 string을 이용하여 답을 구했다. 계산할 때는 숫자를 뒤에서부터 한 자리씩 int로 바꾸어 계산 하였고 계산 완료된 값은 string형으로 배열에 넣어주었다. #include #include #include using namespace std; vector fibonacci; int main() ..