[백준 2448번] 별 찍기 - 11 (C/C++)

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

2448번: 별 찍기 - 11

---

개행 때문에 고민이 필요했던 문제였습니다.

개행은 배열을 이용하여 해결하였습니다.

재귀 시작 전 배열을 공백 문자로 채워주고, 각각의 재귀는 맡은 범위에 삼각형 형태의 별을 저장해주면 됩니다.

 

재귀 함수 탈출 조건은 가장 작은 삼각형을 기준으로 작성하였습니다.

우측 하단의 꼭짓점과 좌측 하단의 꼭짓점의 y좌표 차이가 4이면 가장 작은 삼각형이므로, 재귀 함수의 입력으로 받은 세 꼭짓점을 기준으로 삼각형 형태의 별을 저장해줍니다. 

     *     
    * *    
   *****

가장 작은 삼각형이 아닌 경우, 상단의 삼각형, 하단 좌측, 하단 우측의 삼각형에 대한 재귀를 각각 호출합니다. 

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

전체 코드는 아래와 같습니다. 

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

#define x first
#define y second

// 가장 하단의 별의 개수는 n / 3
// 가장 하단 줄의 수는 5 * (n/3) + (n/3-1)
// n의 최대값은 3072 -> 최하단 줄의 최대 길이는 5 * (3072 / 3) + (3072/3-1) = 6143

char board[3072][6143];

void star(pair<int, int> pos1, pair<int, int> pos2, 
          pair<int, int> pos3){ // pos1은 삼각형 상단의 꼭짓점, pos2는 하단 좌측, pos3는 하단 우측
          
    if(pos3.y - pos2.y == 4){
    	// 첫번째 줄
        board[pos1.x][pos1.y] = '*';	
        // 두번째 줄
        board[pos1.x + 1][pos2.y + 1] = '*'; board[pos1.x + 1][pos3.y - 1] = '*'; 
        // 세번째 줄
        for(int i = pos2.y; i <= pos3.y; i++) board[pos2.x][i] = '*'; 
    }else{
        star(pos1, {(pos1.x + pos2.x) / 2, (pos1.y + pos2.y)/2 + 1}, 
        {(pos1.x + pos2.x) / 2, (pos1.y + pos3.y)/2}); // 상단의 삼각형
        
        star({(pos1.x + pos2.x) / 2 + 1, (pos2.y + pos1.y)/2}, 
        {pos2}, {pos2.x, pos1.y - 1});   //   하단 좌측
        
        star({(pos1.x + pos2.x) / 2 + 1, (pos1.y + pos3.y)/2 + 1}, 
        {pos2.x, pos1.y + 1}, {pos3});   // 하단 우측
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    fill(&board[0][0], &board[3071][6143], ' ');	// 공백 문자로 2차원 배열 초기화
    star({0, (5*(n/3)+(n/3-1)-1) / 2}, {n-1, 0}, {n-1, 5*(n/3)+(n/3-1)-1});

    for(int i = 0; i < n; i++){
        for(int j = 0; j < 5 * (n/3) + (n/3-1); j++)
            cout << board[i][j];
        cout << "\n"; 
    }
}