CT
[BOJ] 25단계 분할 정복
kinggora
2023. 5. 9. 00:44
| 1 | 2630 | 색종이 만들기 |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int white = 0;
private static int blue = 0;
private static int[][] paper;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
paper = new int[N][N];
for(int i = 0; i < N; i++) {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
for(int j = 0; j < N; j++) {
paper[i][j] = Integer.parseInt(tokenizer.nextToken());
}
}
recursion(0, 0, N);
System.out.println(white);
System.out.println(blue);
}
public static void recursion(int x, int y, int size) {
int color = paper[x][y];
boolean isSameColor = true;
for(int i = x; i < x + size; i++) {
for(int j = y; j < y + size; j++) {
if(color != paper[i][j]) {
isSameColor = false;
break;
}
}
}
if(isSameColor) {
if(color == 0) {
white++;
} else {
blue++;
}
} else {
int newSize = size / 2;
recursion(x, y, newSize);
recursion(x + newSize, y, newSize);
recursion(x, y + newSize, newSize);
recursion(x + newSize, y + newSize, newSize);
}
}
}
| 2 | 1992 | 쿼드트리 |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static char[][] image;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
image = new char[N][N];
for(int i = 0; i < N; i++) {
String str = reader.readLine();
for(int j = 0; j < N; j++) {
image[i][j] = str.charAt(j);
}
}
System.out.println(recursion(0, 0, N));
}
public static String recursion(int x, int y, int size) {
char color = image[x][y];
boolean checkColor = true;
for(int i = x; i < x + size; i++) {
for(int j = y; j < y + size; j++) {
if(color != image[i][j]) {
checkColor = false;
break;
}
}
}
if(checkColor) {
return String.valueOf(color);
}
int newSize = size / 2;
StringBuilder sb = new StringBuilder();
sb.append("(")
.append(recursion(x, y, newSize))
.append(recursion(x, y + newSize, newSize))
.append(recursion(x + newSize, y, newSize))
.append(recursion(x + newSize, y + newSize, newSize))
.append(")");
return sb.toString();
}
}*문자열을 병합(정복)하는 과정에서 순서 주의: 왼쪽 위 + 오른쪽 위 + 왼쪽 아래 + 오른쪽 아래
| 3 | 1780 | 종이의 개수 |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[][] paper;
private static int[] count = new int[3];
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
paper = new int[N][N];
for(int i = 0; i < N; i++) {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
for(int j = 0; j < N; j++) {
paper[i][j] = Integer.parseInt(tokenizer.nextToken()) + 1;
}
}
recursion(0, 0, N);
for(int i = 0; i < count.length; i++) {
System.out.println(count[i]);
}
}
public static void recursion(int x, int y, int size) {
if(checkNumber(x, y, size)) {
int idx = paper[x][y];
count[idx]++;
} else {
int newSize = size / 3;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
recursion(x + i * newSize, y + j * newSize, newSize);
}
}
}
}
public static boolean checkNumber(int x, int y, int size) {
if(size == 1) {
return true;
}
int num = paper[x][y];
for(int i = x; i < x + size; i++) {
for(int j = y; j < y + size; j++) {
if(num != paper[i][j]) {
return false;
}
}
}
return true;
}
}*배열을 통해 카운팅하기 위해 입력(-1, 0, 1)을 인덱스 범주(0, 1, 2)로 치환하여 저장함
| 4 | 1629 | 곱셈 |
A, B, C가 모두 2,147,483,647 이하의 자연수일 때 A^B % C 구하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int C;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int A = Integer.parseInt(tokenizer.nextToken());
int B = Integer.parseInt(tokenizer.nextToken());
C = Integer.parseInt(tokenizer.nextToken());
System.out.println(pow(A, B));
}
public static long pow(long num, long n) {
if(n == 1) {
return num % C;
}
long temp = pow(num, n / 2);
if(n % 2 == 0) {
return temp * temp % C;
} else {
return (temp * temp % C * num % C) % C;
}
}
}1. 분할 정복을 이용한 거듭제곱 최적화: C^n
- n이 짝수일 때: C^n/2 * C^n/2
- n이 홀수일 때: C^(n-1)/2 * C^(n-1)/2 * C => (n-1)/2 + (n-1)/2 + 1 = n
2. 모듈러 산술(Modular Arithmetic)의 분배 법칙
- (a + b) mod n = (a mod n + b mod n) mod n
- (a - b) mod n = (a mod n - b mod n) mod n
- (a * b) mod n = (a mod n * b mod n) mod n
| 5 | 11401 | 이항 계수 3 |
분할 정복을 사용한 거듭제곱과 페르마의 소정리를 이용해 곱셈의 역원을 구하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final int MOD = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] split = reader.readLine().split(" ");
int N = Integer.parseInt(split[0]);
int K = Integer.parseInt(split[1]);
//nCk = n! / k!(n-k)!
long numer = factorial(N); // N! % MOD
long denom = factorial(K) * factorial(N-K) % MOD; // (K! % MOD * (N-K)! % MOD) % MOD = K!(N-K)! % MOD
long result = numer * pow(denom, MOD - 2) % MOD; // 페르마의 소정리
System.out.println(result);
}
//N! % MOD 를 구하는 메서드
public static long factorial(int n) {
long result = 1L;
for(int i = 2; i <= n; i++) {
result = result * i % MOD;
}
return result;
}
//C^n % MOD 를 구하는 메서드
public static long pow(long C, int n) {
if(n == 1) {
return C % MOD;
}
long temp = pow(C, n / 2);
if(n % 2 == 0) {
return temp * temp % MOD;
} else {
return (temp * temp % MOD) * C % MOD;
}
}
}
| 6 | 2740 | 행렬 곱셈 |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final int MOD = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] split = reader.readLine().split(" ");
int N = Integer.parseInt(split[0]);
int M = Integer.parseInt(split[1]);
int[][] A = new int[N][M];
for(int i = 0; i < N; i++) {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
for(int j = 0; j < M; j++) {
A[i][j] = Integer.parseInt(tokenizer.nextToken());
}
}
split = reader.readLine().split(" ");
int K = Integer.parseInt(split[1]);
int[][] result = new int[N][K];
for(int i = 0; i < M; i++) {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
for(int j = 0; j < K; j++) {
int n = Integer.parseInt(tokenizer.nextToken());
for(int k = 0; k < N; k++) {
result[k][j] += A[k][i] * n;
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
for(int j = 0; j < K; j++) {
sb.append(result[i][j]).append(" ");
}
sb.append("\n");
}
System.out.print(sb);
}
}
| 7 | 10830 | 행렬 제곱 |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final int MOD = 1000;
private static int N;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
N = Integer.parseInt(tokenizer.nextToken());
long B = Long.parseLong(tokenizer.nextToken());
int[][] matrix = new int[N][N];
for(int i = 0; i < N; i++) {
tokenizer = new StringTokenizer(reader.readLine());
for(int j = 0; j < N; j++) {
matrix[i][j] = Integer.parseInt(tokenizer.nextToken());
}
}
int[][] result = pow(matrix, B);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
sb.append(result[i][j] % MOD).append(" ");
}
sb.append("\n");
}
System.out.print(sb);
}
public static int[][] pow(int[][] matrix, long n) {
if(n == 1) {
return matrix;
}
int[][] temp = pow(matrix, n / 2);
if(n % 2 == 0) {
return multiply(temp, temp);
} else {
return multiply(multiply(temp, temp), matrix);
}
}
public static int[][] multiply(int[][] A, int[][] B) {
int[][] result = new int[N][N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
for(int k = 0; k < N; k++) {
result[i][j] += A[i][k] * B[k][j] % MOD;
}
}
}
return result;
}
}
| 8 | 11444 | 피보나치 수 6 |
행렬({{1,1},{1,0}})의 거듭제곱을 통해 {{Fn+1 Fn}, {Fn, Fn-1}}을 계산
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static final int MOD = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(reader.readLine());
long[][] matrix = {{1, 1}, {1, 0}};
System.out.print(pow(matrix, N - 1)[0][0]);
}
public static long[][] pow(long[][] matrix, long n) {
if(n == 0 || n == 1) {
return matrix;
}
long[][] temp = pow(matrix, n / 2);
if(n % 2 == 0) {
return multiply(temp, temp);
} else {
return multiply(multiply(temp, temp), matrix);
}
}
public static long[][] multiply(long[][] A, long[][] B) {
long[][] result = new long[2][2];
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
for(int k = 0; k < 2; k++) {
result[i][j] += A[i][k] * B[k][j];
}
result[i][j] %= MOD;
}
}
return result;
}
}*N이 1,000,000,000,000,000,000 까지므로 재귀나 배열을 통한 동적계획법을 사용할 수 없다.
*N-1 제곱을 통해 Fn을 계산