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

백준 - 10993

---

풀이

별로 만들어지는 삼각형의 높이와 너비는 각각 2^(N) -1,  2^(N+1) -3이다.

다음은 N=3일 때의 예제이다.

빨간 사각형은 mark_star(x, y, n)을 Recursive Call할 때 해당하는 영영이고, (x, y)는 맨 좌측상단이며, N=1때 는 (x, y)와 영역이 일치하므로 별을 찍어주고 함수를 종료한다.

 

연두색과 하늘색 공간의 별은 다음과 같이 찍었다. 

for (int i = 0; i < width; i++)
    arr[x+(n%2 ? height-1 : 0)][y+i] = '*'; // 연두색
			
for (int i = 0; i < height; i++){
    if (n%2)
        arr[x+i][y+width/2-i] = arr[x+i][y+width/2+i] = '*'; // 하늘색
    else 
        arr[x+i][y+i] = arr[x+i][y+width-i-1] = '*';
}

N의 홀짝여부에 따라서 삼각형 또는 역삼각형 모양으로 별을 찍어주었다.

위의 과정을 통해 하나의 삼각형 모양으로 별을 찍었다면, 다음과 같이 mark_star()을 Recursive Call하면 된다.

mark_star(x+(n%2 ? height/2 : 1), y+(1<<(n-1)), n-1);

 

x, y는 빨간 사각형의 맨 좌측 상단을 가르킨다. 호출하기 전의 N에 따라 좌표를 계산하는 방식이 다르다.

 

별을 출력해줄 때, 삼각형을 그리고 공백이 아닌 개행을 해주어야 한다. 

마찬가지로 N의 홀짝여부에 따라서 출력범위를 알맞게 설정해야 한다.

---

소스코드

#include <stdio.h>
#include <memory.h>
char arr[1023][2045], N;
void mark_star(int x, int y, int n){
    if (n == 1) arr[x][y] = '*';
    else {
        int height = (1<<n) -1, width = (1<<(n+1))-3;
        for (int i = 0; i < width; i++)
            arr[x+(n%2 ? height-1 : 0)][y+i] = '*';
			
        for (int i = 0; i < height; i++){
            if (n%2)
                arr[x+i][y+width/2-i] = arr[x+i][y+width/2+i] = '*';
            else 
                arr[x+i][y+i] = arr[x+i][y+width-i-1] = '*';
        }
		
        mark_star(x+(n%2 ? height/2 : 1), y+(1<<(n-1)), n-1);
    }	
}
int main(){
    scanf("%d", &N);
    int height = (1<<N)-1, width = (1<<N+1)-3;
    memset(arr, 32, sizeof(arr));
    mark_star(0, 0, N);
    for (int i = -height/2; i < height/2 + height%2; i++){
        for (int j = 0; j <= width/4*3 + (N%2 ? i : -i); j++)
            putchar(arr[i+height/2][j]);
        putchar(10);
    }
}

---

출처

10993번: 별 찍기 - 18