[백준/1030/C] 프랙탈 평면

이 문제에서 제시된 N과 s를 곧이곧대로 적용해서 프랙탈전체를 구현하기엔 메모리가 많이 부족할 것이다.

((8^10)^2의 배열을 상상해보았는가.. 나는 못해보았다)

 

그래서 가장 중요한 힌트는 R1 R2 C1 C2의 범위인데 R2-R1, C2-C1이 문제에서 49보다 작은 수로 주어지기 때문에, 프랙탈 전체를 구현하기보다는 각 위치의 원소가 1인지 0인지만 판단하면 되는 문제이다.

 

자 그럼 판단 알고리즘은 어떻게 구현할 수 있을까? 우선 구현된 프랙탈 전체에 들어왔다고 생각해보자 그러면 만약에 전체 프랙탈의 크기를 size라고 할때 각 블록의 사이즈는 size/N일 것이고, 그 블록의 사이즈를 기준으로 한 원소의 위치 cx, cy는 원래의 x, y값에서 size/N을 나눈 값일 것이다. 그러면 그 cx cy가 (N-K)/2과 (N+K)/2사이에 있다면 무조건 가운데 K*K블록 안에 있는 것이니 검정색을 칠해줘야한다. 그렇지 않다면 다시 x,y를 size/N로 나눈 나머지에 대해서 반복해주면 된다. size가 1이 될때까지.

 

#include <stdio.h>

int N,K,R1,R2,C1,C2;
int fractal[50][50];

int mpow(int a, int b){
    int ret = 1;
    while(b--) ret*=a;
    return ret;
}

int isBlack(int x, int y, int size) {
    if (size == 1) return 0; 

    int blockSize = size / N; 
    int cx = x / blockSize;   
    int cy = y / blockSize;

    
    int midStart = (N - K) / 2;
    int midEnd = (N + K) / 2;

    
    if (midStart <= cx && cx < midEnd && midStart <= cy && cy < midEnd)
        return 1;

    
    return isBlack(x % blockSize, y % blockSize, blockSize);
}

int main(){
    int s;
    scanf("%d %d %d %d %d %d %d", &s,&N,&K,&R1,&R2,&C1,&C2);
    for(int i = 0; i<R2-R1+1; i++){
        for(int j = 0; j<C2-C1+1; j++){
            fractal[i][j] = isBlack(i+R1, j+C1, mpow(N,s));
        }
    }
    for(int i = 0; i<R2-R1+1; i++){
        for(int j = 0; j<C2-C1+1; j++){
            printf("%d", fractal[i][j]);
        }
        printf("\n");
    }
    
}