백준 30678 별 안에 별 안에 별 찍기 (C++)

안녕하세요! 오늘부터 [제출한 사람] 수가 적은 백준 문제들 중 제가 푼 것은 포스팅을 하려 합니다

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

예제 입력 1

2

예제 출력 1

            *            
            *            
          *****          
           ***           
           * *           
            *            
            *            
          *****          
           ***           
           * *           
  *    *    *    *    *  
  *    *    *    *    *  
*************************
 ***  ***  ***  ***  *** 
 * *  * *  * *  * *  * * 
       *    *    *       
       *    *    *       
     ***************     
      ***  ***  ***      
      * *  * *  * *      
       *         *       
       *         *       
     *****     *****     
      ***       ***      
      * *       * *      

이 문제는 한창 별찍기 시리즈에 꽂혀 있을 때 발견한 문제인데요,
같은 골드 5 난이도인 별 찍기 - 10과 풀이 방법이 같아서 코드를 조금만 바꿔서 제출했습니다.

#include <cmath>
#include <iostream>

using namespace std;

const int pattern[25] = {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1,
                         1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0};

bool isStar(int x, int y, int patternLength) {
  int newX = (x / (patternLength)) % 5;
  int newY = (y / (patternLength)) % 5;
  int patternIndex = newX + newY * 5;

  if (patternLength == 1)
    return pattern[patternIndex];
  if (pattern[patternIndex])
    return isStar(x, y, patternLength / 5);
  return false;
}

int main() {
  int n;
  cin >> n;
  if (n == 0) {
    cout << "*";
    return 0;
  }
  int powedN = pow(5, n);
  for (int i = 0; i < powedN; i++) {
    for (int j = 0; j < powedN; j++) {
      if (isStar(j, i, powedN / 5))
        cout << "*";
      else
        cout << " ";
    }
    cout << endl;
  }
  return 0;
}

main 함수에는 입출력하는 부분만 있습니다.
n 입력받고 pow 한 후 for문을 돌며 특정 좌표에 star을 찍어야 하면 *, 아니면 공백을 출력합니다.

문제의 핵심 로직인 재귀를 사용하는 부분은 isStar 함수입니다.

가장 큰 좌표계에서 해당 칸이 *인지 확인하고, 공백이면 공백을 리턴하고 *이면 한 차원 더 작은 좌표계에서 해당 칸이 *인지 확인하고, 공백이면 공백을 리턴하고 *이면 한 차원 더 작은 좌표계에서 해당 칸이 *인지 확인하고, 공백이면 공백을 리턴하고 *이면 한 차원 더 작은 좌표계에서 해당 칸이 *인지 확인하고, ....
를 반복하다가, 가장 작은 좌표계면 패턴 배열에서의 값을 그대로 리턴합니다.

개인적으로 재귀랑 DP 문제는 재밌습니다. 옛날에는 canvas에 선을 긋듯이 재귀로 그려야 하는 줄 알았는데, 좌표에 점을 찍을지에 대한 여부를 재귀적으로 판단하는 것이었다고 깨닫고 나니 문제가 잘 풀렸습니다.