본문 바로가기

분할 정복6

백준 2086 피보나치 수의 합 www.acmicpc.net/problem/2086 2086번: 피보나치 수의 합 첫째 줄에 a와 b(1≤a≤b≤9,000,000,000,000,000,000)이 주어진다. www.acmicpc.net a번째 피보나치 수~b번째 피보나치 수의 합을 구하는 문제다. a부터 b까지 모든 피보나치 수의 합을 하나씩 구해서 더하면 O(N) 이므로 a가 1이고 b가 9e18 일 경우 무조건 시간 초과... 따라서 간단한 관찰을 통해 식을 구해야 한다. 1부터 10까지 전부 적어보면 1 2 3 4 5 6 7 8 9 10 1 1 2 3 5 8 13 21 34 55 인데 \(F_5\) 부터 \(F_7\) 까지 구해보면 합은 26이고 이는 \(F_9-F_6\) 인 것을 알 수 있다. 일반화해보면 $$F_{a \;to\;.. 2020. 9. 20.
BOJ 11778 피보나치 수와 최대공약수 www.acmicpc.net/problem/11778 11778번: 피보나치 수와 최대공약수 첫째 줄에 n과 m이 주어진다. n과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 문제들을 풀면서 비슷한 유형들 여러 가지를 푸는데 상당히 재미있다. 이번 문제는 행렬 제곱을 이용한 큰 수의 피보나치 수를 구해서 최대공약수를 구하는 것이다. 이 문제는 각각 n과 m에 대해서 피보나치 수열을 구하고 그 수의 최대 공약수를 구해도 되지만 n과 m을 미리 최대공약수를 구한 뒤 그 수의 피보나치 수를 구해도 된다. #include #include using namespace std; using ll = unsigned long long; const.. 2020. 9. 19.
BOJ 11444 피보나치 수 6 www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번에는 나누는 값이 1000000007이다. www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제에서는 나누는 값이 백만이라 피사노 주기를 통해서 구할 수 있었지만 이번 문제에서는 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. 조건 때문에 피사노 주기를 구하려면 시간 초과가 날 .. 2020. 9. 18.
BOJ 1780 종이의 개수 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 마찬가지로 분할 정복 문제이다. 쿼드 트리 문제와 비슷한데 분할해야 하는 구간만 늘었을 뿐이다. #include #include using namespace std; int mi, ze, pl; vector ar; void f(int x, int y, int n) { int tmp = ar[x][y]; int mod = n / 3; int mod2 = mod * 2; for (int i = x; i .. 2020. 9. 18.
BOJ 1992 쿼드트리 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 분할 정복으로 풀 수 있는 문제다. 처음엔 문제가 이해되지 않았는데 다음날 다시 읽어보니 이해가 됐다. 한 사각형에서 색이 전부 같지 않으면 ( 를 열고 쪼개 주고 전부 같은 색이면 )를 닫는다. 재귀적으로 들어갈 때에 좌상, 우상, 좌하, 우하 순서로 가는것에 주의해야 한다. #include #include using namespace std; string ar[65]; void compress(.. 2020. 9. 18.
BOJ 10830 행렬 제곱 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분할 정복 연습 문제다. 이 문제를 풀기 전에 www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 이 문제를 먼저 풀 줄 알아야 한다. 행렬 a, b가 있다면 a의.. 2020. 9. 16.

티스토리툴바