2448_별찍기 - 11

Explain.

문제보기

Approach

\( N = 3*2^k (k<=10) \) 출력될 총 줄수(높이)

\(C =\) 그려야할 총 삼각형의 개수

$$C=3^{k-1} = (1, 3, 9, 27, ... )$$

위처럼 k값이 증가할때마다 그려야할 삼각형의 개수가 \(3^{k-1}\) 의 형태를 띄고있다. 

이를 활용하여 recursion한 방식으로 의사코드를 작성해보면

input : N = 삼각형의 줄수

output : 삼각형 출력

\(H = N * 2 + 1 \) 밑변의 크기

A[ H * H ] = 삼각형이 저장 될 배열

void recursive(A : array[1...H, 1...H], x : integer, y : integer, h : interger)

if h = 3 then

A[x,y] = *

A[x,y+1] = *

A[x+2,y+1] = *

A[x,y+2] = *

for i=0 to 4 do

A[x+i,y+2] = *

else

recursive(A,x,y+h/2,h/2)

recursive(A,x+h,y+h/2,h/2)

recursive(A,x,y,h/2)

위형태로 작성할 수 있다. 이때 실제 구현시에서는 문제의 삼각형의 모양처럼 x값 앞에 offset값을 줘서 입력해야되는점을 명심해야한다.

Code

#include <stdio.h>
#include <stdlib.h>

void recursive(char **arr, int x, int y,int h, int offset);
void print(char **arr,int w, int h);

int main(void)
{
	char **arr;
	int w,i,h,j;

	scanf("%d", &h);
	
	arr = (char**)malloc(sizeof(*arr) * h);

	w = h * 2 + 1;

	for (i = 0; i < h; ++i)
	{
		arr[i] = (char*)malloc(sizeof(*arr) * w + 1);
		arr[i][w] = '\0';
	}

	for(i=0;i<h;++i)
	{
		for(j=0;j<w;++j)
		{
			arr[i][j] = ' ';
		}
	}

	recursive(arr, 0, 0, h, h-1);
	print(arr, w, h);
	free(arr);
	return 0;
}

void print(char **arr,int w,int h)
{
	int i, j;

	for (i = 0; i < h; ++i)
	{
		printf("%s\n", arr[i]);
	}
}

void recursive(char **arr, int x, int y, int h,int offset)
{
	int i,pad = offset - y;

	if(h==3)
	{
		arr[y][x + pad--] = '*';
		arr[y + 1][x + pad] = '*';
		arr[y + 1][x + 2 + pad--] = '*';
	
		for(i=0;i<5;++i)
			arr[y + 2][x + i + pad] = '*';
		return;
	}
	else
	{
		recursive(arr,x+h,y+h/2,h/2,offset);
		recursive(arr,x,y+h/2,h/2,offset);
		recursive(arr,x,y,h/2,offset);
	}
}