www.acmicpc.net/problem/9471 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000) www.acmicpc.net 피보나치수열을 m으로 나누면 일정한 주기를 띄게 되는데 그 주기의 길이를 찾는 문제이다. 우선 주기마다 규칙이 있을 거라 판단하고 몇 개의 케이스를 돌려보았다. 이 외에도 몇개를 더 살펴봤지만 1, 0 숫자가 나온 뒤에 다시 주기가 나오는 것을 확인할 수 있다. #include using namespace std; int main() { ios::sync_with_stdio(fals..

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 ..

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(..

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의..

www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경�� www.acmicpc.net 이번에도 파라메트릭 서치 문제다. 이번엔 반복문의 시작을 음반에서 가장 큰 값으로 해줘야 하는데, 우리가 찾으려는 값이 무엇인지 알아야 한다. 문제를 잘 읽어보면 우리는 결국 블루레이의 크기를 찾아야 되는데 여기에 이분 탐색이 사용된다. #include #include using namespace std; using ll = long long; int ar[100001], n, m, sum; int main() {..

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색에 대해 공부하는 중이다. 간단한 문제지만 L, R 정하거나 ans값을 찾는 것이 한 번에 되지 않아서 연습해볼 만하다. 정부는 지방마다 각 예산을 할당해야 되는데 예산이 정해져 있어서 우선순위를 둬야 한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상..