데구리 블로그

문제 링크 https://www.acmicpc.net/problem/1003 기본적인 피보나치 문제를 모르거나 시간초과가 문제라면 http://degurii.tistory.com/14?category=755814 를 참고하자. 기존의 피보나치 함수가 $$f(n) = f(n - 2) + f(n - 1)$$ 이므로 $n$일때 호출되는 0과 1의 개수를 $[$0의개수, 1의개수$]_n$ 로 표현해서 단순히 $[i, j]_n = [i, j]_{n - 2} + [i, j]_{n - 1}$ 처럼 쓸 수 있다. 이때, $[i, j] + [x, y] = [i + x, j + y]$로 정의한다. 정답 코드

문제 링크https://www.acmicpc.net/problem/2747 피보나치 수열은 보통 점화식으로 다음과 같이 표현된다.$$f(n) = f(n-2) + f(n-1), (f(0) = 0, f(1) = 1)$$ 이를 재귀함수로 구현하면 이렇게 되고, 위의 코드에서 $n = 6$인 경우 다음 그림처럼 함수가 전개된다. 재귀함수가 $n$을 인자로 호출되면 그 함수는 $n - 1$과 $n - 2$를 인자로 함수를 호출하고, 호출된 각 함수가 계속해서 함수를 두 개씩 호출하게 된다. 결국 시간복잡도가 $O(2^N)$이므로 n 제한이 $n

문제 링크https://www.acmicpc.net/problem/1002 두 터렛의 위치 정보와 각 터렛에서 계산한 상대편 마린과의 거리가 주어질 때 마린이 있을 수 있는 위치를 출력하는 문제다.마린이 있을 수 있는 위치는 '터렛 중심으로부터 거리가 일정한 점들의 집합'이다. 즉, 원으로 볼 수 있다. 터렛이 두 대이므로 두 원끼리 겹치는 점의 개수가 답일 것이다.두 원이 어떤 상황에서 어떻게 겹치는지 알기 위해 다음 6가지 케이스를 보면 된다. 1) 어떤 원이 다른 원에 포함되지 않으면서, 두 원이 접하지 않을 때 2) 외접할 때 3) 두 점에서 만날 때 4) 내접할 때 5) 작은 원이 큰 원 내부에 있으면서, 두 원이 접하지 않을 때 6) 두 원이 같은 원일 때 이제 주어진 원들이 어떤 상태인지 판..

문제링크 https://www.acmicpc.net/problem/1001 A와 B를 받아서 A-B를 출력하자. 정답 코드

문제 링크 https://www.acmicpc.net/problem/1000 A와 B를 받고 A+B를 출력하자. 정답 코드 추가 - 숏코딩