Notice
Recent Posts
Recent Comments
Link
개발자-H 입니다.
BOJ - 종이의 개수 본문
https://www.acmicpc.net/submit/1780/33059203
로그인
www.acmicpc.net
- 날먹 문제이다!
- 색종이 만들기가 4분할 문제를 9분할 문제로 변경하면 쉽게 해결 할 수 있다!
- https://developer-h.tistory.com/entry/BOJ-%EC%83%89%EC%A2%85%EC%9D%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0
import java.io.*;
import java.util.*;
public class Main {
public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception {
int N = Integer.parseInt(br.readLine());
int[][] map = new int[N + 1][N + 1];
for (int i = 0; i < N; i++) {
String[] tokens = br.readLine().split(" ");
for (int j = 0; j < tokens.length; j++) {
map[i][j] = Integer.parseInt(tokens[j]);
}
}
dp(map, 0, 0, N);
System.out.println(minusCount);
System.out.println(zeroCount);
System.out.println(plusCount);
}
private static int minusCount = 0;
private static int zeroCount = 0;
private static int plusCount = 0;
private static void dp(int[][] map, int x, int y, int size) {
// System.out.printf("%d %d %d\n", x, y, size);
if (size == 1) {
int value = map[y][x];
if (value == -1) minusCount++;
if (value == 0) zeroCount++;
if (value == 1) plusCount++;
return;
}
if (isFill(map, x, y, size)) {
return;
}
int nextSize = size / 3;
dp(map, x, y, nextSize);
dp(map, x + nextSize, y, nextSize);
dp(map, x + nextSize * 2, y, nextSize);
dp(map, x , y + nextSize, nextSize);
dp(map, x + nextSize, y + nextSize, nextSize);
dp(map, x + nextSize * 2, y + nextSize, nextSize);
dp(map, x, y + nextSize * 2, nextSize);
dp(map, x + nextSize, y + nextSize * 2, nextSize);
dp(map, x + nextSize * 2, y + nextSize * 2, nextSize);
}
private static boolean isFill(int[][] map, int x, int y, int size) {
int value = map[y][x];
for (int i = y; i < y + size; i++) {
for (int j = x; j < x + size; j++) {
if (value != map[i][j]) {
return false;
}
}
}
if (value == -1) minusCount++;
if (value == 0) zeroCount++;
if (value == 1) plusCount++;
return true;
}
}
'Algorithm > 문제 풀이' 카테고리의 다른 글
BOJ - 쿼드트리 (0) | 2021.09.08 |
---|---|
BOJ - 나는야 포켓몬 마스터 이다솜 (0) | 2021.09.08 |
BOJ - 색종이 만들기 (0) | 2021.09.07 |
BOJ - 최대 힙 (0) | 2021.09.06 |
BOJ - 케빈 베이컨의 6단계 법칙 (0) | 2021.09.05 |