[백준/C++]2447번_ 별 찍기 10

문제는 다음과 같습니다.

규칙을 찾는데에 오래걸렸던 문제였습니다.
하지만, 규칙을 완벽히 찾아 낸 후에는 쉽게 재귀로 풀 수 있는 문제입니다!

N은 3의 거듭제곱으로만 주어지며,
N이 1일때와 N이 2일때의 그림은 다음과 같습니다.

N이 1일때를 보면,
9칸 중 가운데만 비어있는 모양입니다.

이를 확장에서 N이 3일 때를 보면, (가로=9, 세로=9)
N=1인 모양이 채워진 칸으로 볼 때
이 모양이 가운데만 비워져 있고 나머지 8칸은 모두 이 모양으로 채워져 있습니다.

✅즉, N이 커져도 결국 같은 재귀적인 모양의 응용이라고 볼 수 있습니다.✅

제가 푼 풀이의 핵심은 다음과 같습니다.

결국 N이 커지더라도 이는 N=1일때의 응용일 뿐,
N=1의 확장일 뿐입니다.

따라서 어느 위치에 있던, N=1로 옮겨서 생각하면 됩니다.

즉, 저 빨간색 칸으로 비추어 색깔을 칠하면 됩니다.

N=1에서 볼 때, 비어진 칸의 좌표는 (1, 1)입니다.

이 빈 칸의 규칙은 x%3==1 && y%3==1 이 됩니다.
이 경우일 때에는 공백을 출력하면 됩니다.
그리고 이것이 적용되기 위한 선수조건은 x, y좌표가 2 이하가 될 때까지 3으로 나눠줘야 한다는 것입니다.

그리고 입력받은 N에서 3으로 나눈 마지막의 경우는 N이 1이 될 때까지 입니다.
이 때에 x%3==1 && y%3==1을 만족하지 않는다면 *을 출력하면 됩니다.

제 전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int n;

void func(int x, int y, int k){
  if(x%3==1 && y%3==1) cout<<" ";
  else if(k==1) cout<<"*";
  else func(x/3, y/3, k/3);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin>>n;

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      func(i, j, n);
    }
    cout<<"\n";
  }
}