https://www.acmicpc.net/problem/2447
문제
> 재귀적인 패턴으로 별을 찍어 보자.
N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
> 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
***
* *
***
> N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.
> 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************접근
nxn 짜리 색종이가 주어졌을 때, 현 크기를 9등분 한 후 가운데 종이를
전부 구멍을 뚫고, 나머지 종이들을 각각 다시 9등분하고 가운데 종이를
전부 구멍뚫고를 나눈 종이가 3x3짜리 종이가 될 때까지 반복한다.
즉, 재귀를 통해 "종이를 9등분", "9등분한 종이 중 가운데 종이에 구멍뚫기"
를 반복해준다.
이때 각각의 인자로 나눴을 때의 새 크기, 나눴을 때의 첫 시작위치를 잡아줘야한다.
그래야 반복문에서 범위를 잡고 중간값을 찾아 값을 변화시킨다.
이제 각 재귀의 탈출 조건으로 3x3짜리 종이까지 나눠왔을 때를 기준으로 잡아준다.
3x3 짜리면 시작인덱스 기준 1,1(0,0부터시작)위치에 있는 종이에 구멍을 뚫고 재귀를 끝낸다.
그럼 차례대로 젤 작은 종이들이 재귀가 끝나면 점점 3x3짜리끝, 9x9짜리 끝, 27x27짜리 끝
이렇게 된다.
즉, 정리하면 예를 들어 27x27이면 크기가3이 아니므로 일단 9등분을 해서
각각 크기가 9x9인 종이 9개가 나온다. 가운데 종이(5번째 종이)는 전부 구멍내고,
나머지 종이들을 각각 다시 3x3으로 만들어야한다.
첫 9x9종이를 재귀로 넣어 3x3 9개로 쪼개고, 나머지 5번째 제외(구멍내야됨) 재귀로 넣는다.
이제 3x3은 탈출조건에 만족하므로 1,1위치에 구멍내고 재귀 종료.
8개 종이에 전부 구멍내고나면 첫 9x9짜리 종이가 원하는 결과에 맞게 구멍이난다.
그럼 이 과정을 두번째, 세번째..(5번째 제외)..아홉번째 9x9짜리 종이까지 해주면 끝난다.
문제해결
> main문에선 별의 위치를 나타낼 부울형 벡터를 선언하고, 크기를 입력받고,
별 재귀함수 Star에 크기, 첫 시작위치 0,0을 넣어 함수를 호출한다.
그리고 재귀가 끝나면 true인 좌표에 별을 찍고 false는 공백으로 구멍을 낸 출력문을 선언해준다.
> 재귀해줄 부분을 구현한다. 반복문 i와 j를 3까지 범위를 준건, 9등분한 종이 기준 1,1번째(가운데)종이를 구멍처리해주기 위해서다.
그래서 i와 j가 둘다 1일 때, 입력받은 초기좌표 r+새로운크기 * 몇번째 종이인지 해서 다음 종이 직전까지로 인덱스를 해서 이중반복으로 별 벡터에 구멍을 마킹한다.
0,0으로 입력받고 시작했으므로 반복문은, 0+9(27일때)*1 ~ 0+9*(1+2) -> 9~18, 9~18이 된다.
가운데 이외의 종이는 Star(9, 0+9*0, 0+9*0), (9, 0+9*0, 0+9*1)...로 9,0,0 / 9,0,9 / 9,0,18/
9,9,0 / 9,9,18/
9,18,0/ 9,18,9/9,18,18 이렇게 8조각의 초기 좌표가 잡힌다.
> 이제 예를 들어 9,9,18에 대해 3x3으로 쪼개 재귀가 들어갔다고 하자
그럼 각각 3, 9+3*0, 18+3*0 -> 3,9,18 / 3, 9+3*0, 18+3*1 -> 3,9,21 / 3, 9+3*0, 18+3*2 -> 3,9,24 이런식으로 초기 좌표가 잡힌다.
> 이대로 하면 각각 크기별로 중간종이에 구멍이난 형태로 나온다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
vector<vector<bool>> star;
void Star(int size, int r, int c)
{
if (size == 3)
{
for (int i = r; i < r+size; i++)
{
for (int j = c; j < c+size; j++)
{
if (i == r + 1 && j == c + 1)
{
star[i][j] = false;
}
}
}
}
else
{
int Newsize = size / 3;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (i == 1 && j == 1)
{
for (int t = r+Newsize * i; t < r+Newsize * (i + 1); t++)
{
for (int k = c+Newsize * j; k < c+Newsize * (j + 1); k++)
{
star[t][k] = false;
}
}
}
else
Star(Newsize, r+Newsize * i, c+Newsize * j);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
star.assign(N, vector<bool>(N, true));
Star(N, 0, 0);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (star[i][j])
cout << "*";
else
cout << " ";
}
cout << '\n';
}
}
후기
탈출조건과 재귀조건을 설정하는게 어려웠다. 종이 쪼개는걸 재귀로 넣는건 알겠고, 탈출조건을 젤 작은 조각의 구멍을 만들면 까진 생각했는데 각각의 나누기전에 구멍내는걸 어떻게 인덱스를 잡고 어떻게 처리할지 어려웠다.
종이를 전부 그려가며 쪼개다 보니 재귀에 넣기전 처리하고 재귀를 돌려야 맞게 됐다.
각각의 인덱스를 잡아주는것도 문제였다. 처음에 시작으로 들어온 r과 c에 대해 놓치고 인덱스를 단순히 사이즈에 i나 j를 곱해 처리하니 결과가 9x9짜리 종이의 첫 번째 종이만 구멍이 뚫리고 나머진 안뚫려있었다.
기본적으로 r과c가 0,0일때만 처리가 되니까 그런거였다. 그래서 인덱스도 전부 써가면서 인덱스의 규칙을 찾아냈더니 입력받은 r과 c를 각각 가중해주면 되는거였다.
아직도 어지럽다.
