백준 : 2448번, 별 찍기 - 11

문제 주소 : www.acmicpc.net/problem/2448

정답 비율 : 37.161% (2021.02.18 20:52 기준)

2448번: 별 찍기 - 11

 

문제 조건 : 

입력 : N = 3 * 2 ^ k 인 N 값이 주어집니다. (0 <= k <= 10)

출력 : 규칙에 맞게 별을 출력하면 됩니다.

시간 : 1 초

 

문제 풀이 :

문제에서 주어진 예제를 보면 다음과 같습니다. 

N = 24 = 3 * 2 ^ 3 (k = 3)

< N = 23 출력 예제 >

-> 전체를 보면 빨간색 네모 부분이 삼각형을 이루는 것을 확인할 수 있습니다. 빨간색 네모를 보면 노란색 네모 부분으로 구성되고 노란색 부분은 초록색으로 구성되어있는 것을 확인할 수 있습니다.

-> 마침 3 단계로 구성되어 있습니다. 이는 k 값과 같습니다. 따라서 k = 0부터 까지 10까지의 모습을 알 수 있습니다.

 

이를 통하여 다음과 같은 규칙을 찾을 수 있습니다.

 

1. 가로의 길이(x 좌표의 최댓값)는 N * 2 - 1입니다.

2. 세로의 길이(y 좌표의 최댓값)는 N입니다.

3. k = 0일 때 특 별한 규칙이 없습니다. 따라서 각 좌표에 대한 정보를 저장된 배열이 필요합니다.

 

저는 DFS로 구역을 줄여가는 방식으로 문제를 풀었습니다.

 

k = 1일 때를 보면 다음과 같이 구역을 나눌 수 있습니다.

< 구역 나누기 >

이 처럼 6개의 구역으로 나누었습니다. 각 구역에 대하여 다음과 같은 작업을 진행하였습니다.

 

1. 우선 현재 위치가 1, 2, 3에 속하는 4, 5, 6에 속하는 지를 확인 합니다. (현재 위치의 y 좌표만 확인하면 됩니다.)

2. 1, 2, 3에 속하는 경우 2구역 여부인지를 확인하면 됩니다. 그 외 영역은 공백을 출력하면 됩니다.  1과 3구역의 모양을 보면 정사각형입니다. 따라서 이를 이용하여 2 구역의 시작과 끝인 x의 좌표를 구할 수 있습니다. (시작 좌표 : N / 3, 끝 좌표 : if의 조건이 x <= end_x 일 때 N * 2 - N / 2 - 2이고 x < end_x 일 때 N * 2 - N / 2 - 1)

3. 4, 5, 6에 속하는 경우에는 4, 5, 6에 대한 모든 경우를 확인해야 합니다. 이때 5구역은 직선이며 x의 좌표는 N - 1 임을 확인할 수 있습니다. 

 

이로써 좌표가 주어질 때 모든 구역을 구분할 수 있게 되었습니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

char basic[15] = "  *   * * *****";

void dfs(int depth, int x, int y, int N)
{
	if(depth == 0)
	{
		printf("%c", basic[y * 5 + x]);
	}
	else
	{
		int y_area = (y < N / 2 ? 0 : 1);
		
		if(y_area) //area 4 val = 1, 5 val = 0, 6 val = 2
		{
			int x_area = (x < N - 1 ? 1 : (x > N - 1 ? 2 : 0));
			
			if(x_area == 1)
				dfs(depth - 1, x, y - N / 2, N / 2);
			else if(x_area == 2)
				dfs(depth - 1, x - N, y - N / 2, N / 2);
			else	
				printf(" ");
		}
		else //area 1 val = 0, 2 val = 1, 3 val = 0
		{
			int x_area = (x < N / 2 ? 0 : (x > N * 2 - N / 2 - 2 ? 0 : 1));
			
			if(x_area)
				dfs(depth - 1, x - N / 2, y, N / 2);
			else 
				printf(" ");
		}
	}
}


int main()
{
	int i = -1, j = -1, N = -1, depth = -1;
	
	scanf("%d", &N);
	
	for(i = N / 3; i; i /= 2)
		depth++;
	
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N * 2 - 1; j++)
			dfs(depth, j, i, N);
		puts("");
	}
} 

 

끝~~