[백준][C++] 10993 별 찍기 - 18

www.acmicpc.net/problem/10993

10993번: 별 찍기 - 18

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    1. 짝수일 때, 역삼각형이고 홀수일 때, 삼각형 모양이다.

    2. n에 따라 가로는 1 + 2^0 + 2^1 + ... + 2^n이고, 세로는 1 + 2^0 + 2^1 + ... + 2^(n-1)이다.

    3. 본인은 바깥부터 안으로 *을 표시하기로 했다. 따라서, 바깥에 *을 표시하고 다음 *을 그릴 구역을 선정한다.

        3-1. 구역은 가로는 x1~x2, 세로는 y1~y2로 정했다.

        3-2. x1은 처음에 0에서 시작해서 계속 2^(i-1)만큼 오른쪽(+)으로 이동한다. 

        3-3. x2는 처음에 가로 최대지점에서 시작해서 계속 2^(i-1)왼쪽(-)으로 이동한다.

        3-4. y1은 짝수에서 홀수로 변경될 때, 기존 y1에 +1되어 이동한다. 홀수에서 짝수로 변경될 때, y1에 2^(i-1) -1 만큼 아래로(+)이동한다.

        3-5. y2는 짝수에서 홀수로 변경될 때, 기존 y2에 2^(i-1) -1만큼 위(-)로 이동한다. 홀수에서 짝수로 변경될 때, y2에 -1되어 이동한다.

    

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
int w, h;
char mat[3000][3000];
 
void print(int n, int w, int h){
    // 오른쪽에 빈 공간 없이 출력하기 
     
    // 삼각형 모양으로 출력하기  
    if(n%2!=0){
        w = w/2 + 1;
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cout << mat[i][j];
            }    
            cout << endl;
            w++;
        }
    }
    // 역삼각형 모양으로 출력하기  
    else{
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cout << mat[i][j];
            }
            cout << endl;
            w--;
        }
    }
}
 
 
void dfs(int n, int x1, int x2, int y1, int y2){
    if(n==0) return;
    
    // 원래 좌표 값  
    int ox1 = x1;
    int ox2 = x2;
    int oy1 = y1;
    int oy2 = y2;
    
    // 역삼각형일 경우  
    if(n%2==0){
        for(int i=y1; i<y2; i++){
            // 처음이면 모두 *표시  
            if(i==y1){
                for(int j=x1; j<x2; j++){
                    mat[i][j] = '*';
                }
            }
            // 끝에만 *표시  
            else{
                mat[i][x1] = '*';
                mat[i][x2-1] = '*';
            }
            // 끝에 *표시 하기 위해서 범위 축소  
            x1++;
            x2--;
 
        }
        // 역삼각형이니 윗쪽 좌표 구해서 보내기  
        dfs(n-1, ox1+pow(2, n-1), ox2-pow(2, n-1), oy1+1, oy2-(pow(2, n-1)-1));
    }
    else {
        for(int i=y2-1; i>=y1; i--){
            if(i==y2-1){
                for(int j=x1; j<x2; j++){
                    mat[i][j] = '*';
                }
            }
            else{
                mat[i][x1] = '*';
                mat[i][x2-1] = '*';
            }
            
            x1++;
            x2--;
 
        }
        // 삼각형이니 아랫쪽 좌표 구해서 보내기  
        dfs(n-1, ox1+pow(2, n-1), ox2-pow(2, n-1), oy1+(pow(2, n-1)-1), oy2-1);
    }
}
 
 
int main(void){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int n;
    cin >> n;
    
    w = 1;
    h = 1;
    // 밑변 높이 구하기  
    for(int i=2; i<=n; i++){
        w += pow(2, i);
        h += pow(2, i-1);
    }
    // 초기화  
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            mat[i][j] = ' ';
        }
    }
 
    dfs(n, 0, w, 0, h);
    print(n, w, h);
}
 

 

 

 

시행착오

    - 배열을 사용하지 않고 출력할 수 있는 방법을 생각해보았다. 왜냐하면, 메모리를 과하게 사용하고 싶지 않았기 때문이다. 그러나 방법을 알아내기 쉽지 않아서 배열에 *표시를 저장하는 재귀함수를 이용하기로 했다.

    - 패턴을 파악해야 했다. n에 따라 가로와 세로의 크기 조정. x1, x2, y1, y2의 변화를 하나하나 써보면서 찾았다.