[C++] 백준 2447 - 별 찍기 10

www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

<풀이>

1. 정사각형 한 변의 길이인 N을 입력받는다.

2. N x N 정사각형에 주어진 패턴대로 출력한다.

 

<해법>

1. 주어진 패턴 분석하는 방법

=> 주어진 패턴은 총 9부분으로 나누어서 생각할 수 있습니다. 나누어진 9부분을 또 더 탐색해야할 8부분과 탐색할 필요없는 가운데 부분으로 나눌 수 있습니다. 

 

2. N x N 정사각형 출력하는 방법

=> 분할 정복을 끝냈다면, 이제는 출력을 해야 합니다. 저는 N x N 정사각형 배열을 만들어서, 배열에 분할 정복된 패턴을 담아주는 방식으로 구현하였습니다.

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int N;
char map[2200][2200];
 
//x,y : 좌표, n : 한 변의 길이
void makeStar(int x, int y, int n) {
 
    //더이상 나눌 수 없는 지점
    if (n == 1) {
        map[x][y] = '*';
        return;
    }
 
    int div = n / 3;
 
    //9부분으로 나누기
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
 
            //가운데 지점은 빈 칸으로 채우기
            if (i % 3 == 1 && j % 3 == 1) {
 
                for (int k = 0; k < div; k++) {
                    for (int l = 0; l < div; l++) {
                        map[x + i + k][y + j + l] = ' ';
                    }
                }
 
                continue;
            }
 
            //나머지 8부분 탐색
            makeStar(x + div * i, y + div * j, div);
        }
    }
}
 
int main() {
 
    //초기화
    N = 0;
    memset(map, '#', sizeof(map));
 
    //입력
    cin >> N;
 
    //해법
    /*
    9등분으로 나누어서 분할 정복
    */
    makeStar(0, 0, N);
 
    //출력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << map[i][j];
        }
        cout << "\n";
    }
 
    //종료
    return 0;
}

 

분할 정복과 구현에 대해 알아볼 수 있는 문제였습니다.