컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 https://kimmessi.tistory.com/122 이 문제에서 모듈러의 값만 바꿔주면 된다. 소스 코드 #include #define MOD 1000000 using namespace std; long long n; map dOcagne_map; long long dOcagne(long long x){ if(x == 0 || x == 1) return x; long long y = x/2; long long tmp_1, tmp_2, result; /..

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 도가뉴 항등식을 이용해서 푸는 분할정복 문제였다. 도가뉴 항등식 $$ F_{m+n} = F_{m-1}F_{n} + F_{m}F_{n+1} $$ 위의 항등식을 활용해 $m+n$이 짝수일 때와 홀수일 때를 나눠서 점화식을 이용해 분할정복을 해준다. 이때 맵을 통해서 불필요한 계산을 방지하기 위해 한 번 계산한 값은 저장해주고 다음에 쓰일 때 바로 맵에서 꺼내 쓰는 다이나믹 프로그래밍도 쓰인다. 모듈러 계산도 중요하다. 소스 코드 #include #define..

https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 이 문제를 처음에 풀 때는 간단하게 while문을 이용해 풀려고 했지만, 시간초과가 나는 것이다. #include using namespace std; int main() { int a, b, v, sum = 0, cnt = 0; cin >> a >> b >> v; while (true) { cnt++; sum += a; if (sum >= v) break; sum -= b; ..