본문 바로가기

분할정복

 (4)
[백준] 10830 행렬 제곱 문제링크: www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이전에 풀었던 행렬 곱셈과 분할정복을 활용했다. 그런데, 임시 배열을 써서 복사행위를 해서 코드가 길어졌다. 다른 분의 코드를 보니 배열을 인자로 넘겨서 하더라. 나중에 다시 풀어보고 활용 해볼 것이다. import java.io.*; import java.util.*; public class Main { public static int [][]A; public static int N; public static l..
[백준] 11401 이항계수3 문제링크: www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 예전에 들어본 적 있어서 페르마의 소정리로 풀어야 한다는 것은 기억했지만 정리가 기억나지 않았다. 적어두고 반복해봐야겠다. import java.io.*; import java.util.*; public class Main { public static final long MOD = 1000000007; public static long fac[]; public static long power(long num,long cnt..
[백준] 1629 곱셈 문제링크: www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net power import java.io.*; import java.util.*; public class Main { public static long N,M,K; public static long power(long num,long cnt) { if(cnt==0) return 1; long temp = power(num,cnt/2); temp = temp*temp % K; if(cnt%2==1) { temp*=num % K; } return temp % K; } pu..
[백준] 1992 쿼드트리 문제링크: www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 문제를 읽는 순간 분할정복임을 알았다. import java.io.*; import java.util.*; public class Main { public static int N; public static char [][]board; public static void divide_q(int start_y, int start_x, int square_size) { if(square_size..

티스토리툴바