분할정복

링크https://www.acmicpc.net/problem/1629    문제자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.    입력첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.    출력첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.    예제 입력 110 11 12   예제 출력 14    아이디어 스케치분할 정복 알고리즘을 사용하지 않을 경우 시간 초과가 발생한다. 분할 정복 알고리즘을 사용하여 거듭제곱을 계산하기 위해서는 다음과 같은 아이디어가 필요하다.  \(C^n\)은 위 식과 같이 분할할 수 있다. ..

링크https://www.acmicpc.net/problem/1780    문제N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.    입력첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다..