[백준] 프렉탈 평면

https://www.acmicpc.net/problem/1030

1030번: 프렉탈 평면

 

1. 문제 이해

프랙탈 평면은 맨 처음 가장 큰 흰색 정사각형을 시작으로 규칙에 따라 흰색 정사각형과, 검은색 정사각형으로 쪼개지게 됩니다. 문제에서는 커진다고 표현했는데 점점 쪼개진다고 봐도 무방합니다. 한번 검정색인 정사각형은 쪼개져도 정사각형이 되고 흰색 정사각형은 시간에 지남에 따라 쪼개지면서 가운데 K X K 정사각형은 검은색으로 칠해지게 됩니다. 

2. 문제 접근

첫번째 풀이: 분할정복

출력해야하는 직사각형의 크기가 최대 50 * 50 밖에 되지 않기 때문에 하나의 좌표가 흰색인지 검은색인지 판단해주면 됩니다. 현재 사이즈 N * N 등분한 다음 찾고자 하는 좌표가 들어있는 칸이 검정색이면 1을 출력하고 그렇지 않으면 재귀를 통해 다음 사이즈로 넘어가게 됩니다. 

 

검정색 칸인지 판별하는 방법은 사각형의 정중앙에 위치하기  때문에 start + (현재 사이즈 - (k X 다음 사이즈)) // 2 가 되게 됩니다.

3. 풀이

import sys, heapq
from collections import defaultdict

#sys.stdin = open("input.txt")

input = sys.stdin.readline

s, n, k, r1, r2, c1, c2 = tuple(map(int, input().split()))

if s == 0:
    print(0)
    sys.exit(0)

def dq(startY, startX, length, y, x):
    # 기저 조건
    if length == 1:
        return 0

    next_length = length // n

    bStartY, bStartX = startY + (length - (k * next_length)) // 2, startX + (length - (k * next_length)) // 2

    for i in range(startY, startY + length, next_length):
        for j in range(startX, startX + length, next_length):
            # 범위 내에 있는 경우
            if i <= y < i + next_length and j <= x < j + next_length:
                # 검정 영역이면 리턴 1
                if bStartY <= y < bStartY + (k * next_length) and bStartX <= x < bStartX + (k * next_length):
                    return 1

                # 흰 영역이면 dq로 파고 들어간다.
                ret =  dq(i, j, next_length, y, x)
                return ret

for i in range(r1, r2 + 1):
    for j in range(c1, c2 + 1):
        print(dq(0, 0,  n ** s, i, j), end="")
    print()

4. 회고

분할정복을 통해 풀기는 했지만 식을 도출해내는데까지 시간이 조금 걸렸던 문제