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

• 풀이 방법

• 최종 코드

난이도 : 골드 5

시간 : 30분 소요

 

 

풀이 방법

 

자료구조 강의 때 많이 본 유형이다.
H-tree 구현했을 때처럼 접근해봤다.

먼저 map[3^8][3^8]을 설정하여 재귀가 끝나고, 순서대로 출력하면 답이 되도록 하였다.

이 문제의 재귀함수 포인트는

1. 들어온 입력값을 3으로 나누고, 9번 재귀함수를 호출한다.
2. 가운데는 비워야 하기 때문에 if문으로 좌표가 (중간값, 중간값)이 되면 아무것도 처리하지 않는다.
3. 재귀함수의 파라미터가 3일 경우 해당 좌표부터 3x3를 1로 저장한다.
4. 재귀함수가 모두 끝나면 1일 경우만 '*' 를 출력한다.

 

최종 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstring>

using namespace std;

char map[6562][6562];
int N;

void star(int x, int y, int num){
    
    if(num == 3){
        for(int i=x; i<x+3; i++){
            for(int j=y; j<y+3; j++){
                if(i == x+1 && j == y+1)
                    continue;
                map[i][j] = 1;
            }
        }
        
        return;
    }
    
    int tmp = num/3;
    for(int i=x; i<x+num; i+=tmp){
        for(int j=y; j<y+num; j+=tmp){
            if(i == x+tmp && j == y+tmp)
                continue;
            star(i,j,tmp);
        }
    }
    
}

int main(void){
    scanf("%d", &N);
    
    star(0, 0, N);
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(map[i][j] == 1)
                printf("*");
            else
                printf(" ");
        }
        printf("\n");
    }
    
    
}