#문제
레벨: S2
알고리즘: 분할정복(기본)
풀이시간: 20분
힌트 참조 유무: 무
https://www.acmicpc.net/problem/1780
#문제 풀이
이 문제는 피보나치 문제(easy)와 마찬가지로 분할정복의 기초 문제이다. (개인적인 생각으로는 그렇다.)
분할정복 문제를 풀게 된다면 반드시 이 문제는 풀어보고 갔으면 좋겠다.
분할정복 말은 거창하지만 가장 작은 문제로 쪼갤 수 있을 때까지 쪼갠 후 작은 문제들을 풀이하는 것이다.
이 문제에서는 풀어주세요 ~ 라고 말하는 것처럼 문제를 쪼개는게 직접적으로 나와있다.
큰 정사각형을 모든 수가 같을 때까지 9등분으로 나누면 되는 것이다. 쉽지 않은가. 나머지는 코드 참고 바란다.
#풀이 코드
import java.util.*;
import java.io.*;
class Main {
static int ansM1 = 0;
static int ans0 = 0;
static int ans1 = 0;
static int[][] map;
public static void main(String[] args) throws IOException {
//입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(N, 0, 0);
bw.write(ansM1 +"\n");
bw.write(ans0 +"\n");
bw.write(ans1 +"\n");
bw.flush();
bw.close();
br.close();
}
//쪼갤 수 있을 때까지 쪼갠다
public static void dfs(int n, int startX, int startY) {
if(check(n, startX, startY)) {
plusAnswer(map[startX][startY]);
return;
}
for(int i = startX; i < startX+n; i+=n/3) {
for(int j = startY; j < startY+n; j+=n/3) {
dfs(n/3, i, j);
}
}
}
//사각형이 다 같은 요소로 이뤄져있는지 확인
public static boolean check(int n, int startX, int startY) {
int startNumber = map[startX][startY];
for(int i = startX; i < startX+n; i++){
for(int j = startY; j < startY+n; j++) {
if(map[i][j] != startNumber)
return false;
}
}
return true;
}
//수에 따라 변수 ++
public static void plusAnswer(int n) {
if(n == -1)
ansM1++;
else if(n == 0)
ans0++;
else if(n == 1)
ans1++;
}
}
'알고리즘 > 분할' 카테고리의 다른 글
[백준 2261] 가장 가까운 두 점 / 자바 / 분할정복 or 라인스위핑 (0) | 2024.08.29 |
---|---|
[백준 2263] 트리의 순회 / 자바 /분할정복 (0) | 2024.07.02 |
[백준 2630] 색종이 만들기/ 자바 (1) | 2024.07.02 |