INFO
1. 문제 이해
핵심 요구사항
- 단위 시간이 진행될 때마다
- 모든 정사각형이 NxN개의 정사각형으로 분리
- 흰색 정사각형이 나누어진 경우, 가운데 KxK 정사각형을 검정색으로 칠함.
- 시간 s일 때, R1행 C1열부터 R2행 C2열까지의 모습을 출력
제한 조건
- 변수 범위
- 0 ≤ s ≤ 10
- 3 ≤ N ≤ 8
- 1 ≤ K ≤ N - 2
- (N - K) mod 2 = 0
- 0 ≤ R1, R2, C1, C2 ≤ Ns - 1
- R1 ≤ R2 ≤ R1 + 49
- C1 ≤ C2 ≤ C1 +49
- 시간
- 2초
- 메모리
- 128MB → → 개의 int 저장 가능
2. 사고의 흐름 (Thinking)
-
❌ 1차 시도: 분할정복 + 전체 배열
- 배열 = s초 시간 후 존재하는 모든 정사각형을 만듦.
- 분할정복으로 s번 재귀를 내려가면서 색깔을 칠함.
- 매개변수를 통한 부모 색상 전파 → 부모가 검정이면 자식도 검점
- ⇒ 메모리 초과
- 분리된 배열 전부 만들면,
- 128MB에 수용 불가
-
❌ 2차 시도: 분할정복 + 부분배열
- 배열 = 출력할 위치의 정사각형들만 만듦.
- 재귀를 돌면서, 해당 범위에 대한
- ⇒ 시간 초과
- 재귀가 너무 깊게 내려가서 생기는 문제
- 출력범위를 벗어난 부분은 재귀를 이어나갈 필요가 없음
-
✅ 3차 시도: 분할정복 + 부분배열 + 가지치기
- R1 ~ R2 / C1 ~ C2 범위를 넘어가는 경우
RETURN
- R1 ~ R2 / C1 ~ C2 범위를 넘어가는 경우
3. 풀이 및 코드 (Solution)
import java.io.*;
public class Main {
static int s, N, K, R1, R2, C1, C2, ns;
static int[][] result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
s = Integer.parseInt(temp[0]);
N = Integer.parseInt(temp[1]);
K = Integer.parseInt(temp[2]);
R1 = Integer.parseInt(temp[3]);
R2 = Integer.parseInt(temp[4]);
C1 = Integer.parseInt(temp[5]);
C2 = Integer.parseInt(temp[6]);
ns = (int) Math.pow(N,s);
result = new int[R2-R1+1][C2-C1+1];
coloring(0,0, ns, 0);
StringBuilder sb;
for (int i=0; i < R2-R1+1; i++) {
sb = new StringBuilder();
for (int j=0; j < C2-C1+1; j++) {
sb.append(result[i][j]);
}
System.out.println(sb);
}
}
static void coloring(int sx, int sy, int len, int color) {
if (sx > R2 || sy > C2 || sx+len <= R1 || sy+len <= C1)
return;
if (len == 1) {
result[sx-R1][sy-C1] = color;
return;
}
// 가운데 kxk 사각형 위치 구하기
int new_len = len / N;
int black = ((N - K) / 2) * new_len;
// 가운데
for (int i=0; i < len; i+=new_len) {
for (int j=0; j<len; j+=new_len) {
int new_color = color;
if (i >= black && i < black+(K*new_len) && j >= black && j < black+(K*new_len)){
new_color = 1;
}
coloring(sx+i, sy+j, new_len, new_color);
}
}
}
}- 시간 복잡도:
- 재귀 깊이 = s
- 재귀 너비(가지치기를 통해 줄어듬) = 출력범위
- 각 재귀 별 연산 수 = 대략
- 공간 복잡도:
4. 회고 (Retrospective)
- 공간 복잡도 체크 잘하기: 시간 복잡도에 비해 자주 등장하는 포인트가 아니어서, 간과하기 쉬움. 특히나 지수 형태의 크기를 가진 공간이 나오면 계산 실수 하지 말고 잘하기
- 좌표 기반 가지치기: 필요 없는, 혹은 이미 결정된 값은 과감히 버리거나 한번에 처리하기