[ 백준 1030 ] 프렉탈 평면 (c/c++)

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

 

 

[ 문제 요약 ]

시간이 1 진행되었을 때, N×N개의 크기가 동일한 단위 정사각형으로 나누어진다. 만약 나누어진 정사각형이 흰색이라면 가운데 K×K 정사각형이 검정색으로 채워진다. 시간이 S만큼 진행되었을 때 R1행 C1열부터 R2행 C2열까지의 모습을 출력한다.

 

 

[ 문제 풀이 ]

1. S만큼 진행되었을 때 R1행 C1열부터 R2행 C2열까지의 각각의 단위 정사각형이 무엇인지 구하면 된다.

2. 만약 시간이 진행되는 동안 한번이라도 위치가 가운데 K * K 정사각형에 속해서 검은 사각형이 된다면 무조건 검은 정사각형이다.

3. 만약 한번 시간을 진행했는데 흰색 정사각형이라면 위 조건에 따라서 다시 작은 사각형으로 보고 나누어서 검은 정사각형이 되는지 확인한다.

4. 만약 사각형의 길이가 1이라면 흰색 정사각형이다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int S, N, K, R1, R2, C1, C2, len = 1;

int Find(int l, int x, int y){
    if (l == 1) return 0;
    int max_l = l / N;
    if (x >= max_l * (N - K) / 2 && x < max_l * (N + K) / 2 && y >= max_l * (N - K) / 2 && y < max_l * (N + K) / 2) return 1;
    return Find(max_l, x % max_l, y % max_l);
}

int main() {
    cin >> S >> N >> K >> R1 >> R2 >> C1 >> C2;
    if (S == 0) cout << 0;
    else {
        for (int i=0; i<S; i++) len *= N;
        for (int i=R1; i<=R2; i++){
            for (int j=C1; j<=C2; j++) cout << Find(len, i, j);
            cout << "\n";
        } 
    }
    return 0;
}

 

 

[ 주의할 점 ]

만약 시간이 흐르지 않았다면 무조건 흰색 정사각형 하나만을 출력한다.