(백준 2447번 별 찍기 - 10 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 4탄

어제 디버깅하다 못 끝낸 별 찍기 - 10을 고쳤다! 역시 아침이 되니 머리가 아주 맑아지는군🎵

 

이전 포스팅은 여기에!↓

2024.01.09 - [알고리즘] - (백준 1629번 곱셈 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 3탄

(백준 1629번 곱셈 C++) 라이님 블로그 대회 알고리즘 따라잡기 4) 분할 정복(Divide and Conquer) 3탄

 

백준 2447번

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

분할 정복의 정석같은 문제! 일단 코드를 보면 다음과 같다. 

//백준 2447번
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <utility>
#include <vector>

// 한 변의 길이 3^N, (x, y)가 가장 왼쪽 상단에 위치한 점 
void PrintStar(char** Arr, int N, int x, int y);
void FillBlank(char** Arr, int N, int x, int y);

int main() {
	int N;
	scanf("%d", &N);
	char** Arr = new char* [N];
	for(int i = 0; i< N; i++) Arr[i] = new char[N];
	
	PrintStar(Arr, N, 0, 0);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%c", Arr[i][j]);
		}
		printf("\n");
	}

	for (int i = 0; i < N; i++) delete[]Arr[i];
	delete[]Arr;

	return 0;
}
void FillBlank(char** Arr, int N, int x, int y) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			Arr[x + i][y + j] = char(32);
		}
	}
	return;
}

void PrintStar(char** Arr, int N, int x, int y) {
	//Base case : 한 변의 길이 3^1일 때 
	if (N == 3) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (i == 1 and j == 1) Arr[x+i][y+j] = char(32);
				else Arr[x+i][y+j] = char(42);
				
			}
		}
		return;
	}
	std::vector<std::pair<int, int>> StartingPoint = {
		{0,0}, {0, N / 3}, {0, N * 2 / 3},
		{N / 3, 0}, {N / 3, N / 3}, {N / 3, N * 2 / 3},
		{N * 2 / 3, 0}, { N * 2 / 3, N / 3 }, { N * 2 / 3, N * 2 / 3 }
	};
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == 1 and j == 1) FillBlank(Arr, N / 3, x + StartingPoint[i * 3 + j].first, y + StartingPoint[i * 3 + j].second);
			else PrintStar(Arr, N / 3, x+StartingPoint[i * 3 + j].first, y+StartingPoint[i * 3 + j].second);
		}
	}
	
	return;
}

 

어제 아침에 

꾸엑 - 외마디의 비명과 함께 출근했었는데, 이렇게 보내니 김모기씨가 하는 말이 보통 경험상 한자의 출력은 쓰레기 값이 들어간 경우가 많다고 말해줬다.

 

나의 실수 및 주의할 점

1. N==3인 경우 return의 위치가 잘못되어서 배열의 업데이트가 안되었다.  N == 3인 베이스 케이스에도 문제가 있어 다른 예제도 작동하지 않았다.

2. (기준점 x, 기준점 y)를 기준으로 작동하게끔 코드를 짜났으면서도 (x,y)를 자주 깜빡하게 된다. 이 부분을 확인해보면 좋을 듯!

3. (아스키코드) char(32)는 공백을, char(42)는 *를 의미한다. 

 

얼마만에 한 방에 맞은 문제인가ㅠㅠ흙흙 너무 신난다🤭