백준 문제풀이 : (2447) 별 찍기 - 10 - C/C++

문제 : https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

시간 제한	메모리 제한	난이도	알고리즘 분류
1초	256 MB	Gold 5	분할정복, 재귀

 

 

문제

 

 

풀이

3을 N으로 줬을 때 출력되는 패턴이 재귀적으로 반복되고 있다. 패턴을 분석해보면 아래와 같다.

 

1. 한 변의 출력 개수는 N개이다. (* or ' ')

2. N*N 개의 출력으로 이루어진 크기 N의 패턴을 한 줄에 3 부분 씩 9 부분으로 나누면, 각 부분에서 동일한 패턴이 반복된다. 

3. 2에서의 동일한 패턴이란, 

 

1  2  3

4  5  6

7  8  9

 

순으로 9개의 부분에 번호를 매겼을 때 5번 칸에서는 공백을, 다른 칸에서는 "*"을 출력함을 말한다. 

 

따라서 1부터 9 부분까지 순차적으로 방문하는 반복문을 만들고, 5번째 칸일 경우에는 공백을, 그 외의 칸에서는 "*"을 출력하는 재귀문을 넣어준다.

 

 

코드 작성

#include <iostream>
#include <vector>

using namespace std;
bool map[6561][6561];

void drawSquare(int N, bool tf, int x, int y) {
    if (N==1) {
        map[x][y]=tf;
        return ;
    }
    
    for (int i=0 ; i<N ; i+=N/3) { //2차 반복으로 1~9번까지의 칸들에 순차 방문
        for (int j=0 ; j<N ; j+=N/3) {
            if ((i==N/3 && j==N/3) || tf==false) {
              drawSquare(N/3, false, x+i, y+j); 
              // 5번째 칸이면 공백 칸이므로 false로 진입. 
        	  // 위 재귀문의 하위 재귀에서는 전부 false로 처리해야하기 때문에,
              // tf==false 조건 추가
            } else drawSquare(N/3, true, x+i, y+j);
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);
    
    drawSquare(N, true, 0, 0);
    
    for (int i=0 ; i<N ; i++) {
        for (int j=0 ; j<N ; j++) {
            printf("%c", (map[i][j]==true) ? '*' : ' ');
        }
        printf("\n");
    }
 }

 

 

END.