2447번: 별 찍기 - 10(백준 C++)

2447번: 별 찍기 - 10 링크

코드

#include <iostream>
using namespace std;

char arr[2187][2187];

void init(){
  for(int i=0; i<2187; i++){
    for(int j=0; j<2187; j++){
      arr[i][j] = ' ';
    }
  }
}


void solve(int n, int x, int y){
  if(n == 1) {
    arr[x][y] = '*';
  }
  else{
    for(int i=x; i<x+n; i+=n/3){
      for(int j=y; j<y+n; j+=n/3){
        if(i == (x + n/3) && j == (y + n/3)) continue;
        solve(n/3, i, j);
      }
    }
  }
}
int main(){
  init();
  int n;
  cin >> n;
  solve(n, 0, 0);

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cout << arr[i][j];
    }
    cout << "\n";
  }
}

사견

재귀함수를 이용한 별 찍기 문제.

입력

우선 입력을 보자.
입력 N은 3의 거듭제곱이 주어진다.

N = 3^k 라고 할 때, k의 범위는 1 <= k < 8이다.

그리고 주어진 문제에 따라 찍어야 하는 별의 범위는 N X N 사이즈이다.

즉, 우선 기본적으로

char arr[2187][2187];

이라는 도화지를 준비하면 문제 풀이에 용이하다.
( 3^7 = 2187, 즉 주어질 수 있는 N에 따른 최대범위 배열)

void init(){
  for(int i=0; i<2187; i++){
    for(int j=0; j<2187; j++){
      arr[i][j] = ' ';
    }
  }
}

이후 그 도화지의 모든 칸에 ' ' , 공백을 넣어준다.

규칙

재귀함수 문제를 풀 때에는 반복되는 규칙성을 찾아내는 것이 중요하다.

이 문제 같은 경우에는

주어진 N에 대해 이러한 구조를 가지고, 위 그림에서 보면 각 네모칸 안의 N이 3보다 크다면 그 안에서 또 위와같은 정사각형이 있는 형태이다.

이러한 규칙에 따라 재귀함수로 N == 1일때 별을 찍어주는 형태로 코드를 짜면

void solve(int n, int x, int y){
  if(n == 1) {
    arr[x][y] = '*';
  }
  else{
    for(int i=x; i<x+n; i+=n/3){
      for(int j=y; j<y+n; j+=n/3){
        if(i == (x + n/3) && j == (y + n/3)) continue;
        solve(n/3, i, j);
      }
    }
  }
}

이렇게 된다.

재귀함수가 끝나면, 배열에 별이 다 찍혀있으므로, N의 크기에 맞춰서 출력해주면 된다.