백준 2448 - 별 찍기 - 11(C++)

문제

N이 주어졌을 때 첫째 줄부터 N번째 줄까지 별을 출력한다.

 

이때 규칙에 따라 출력해야 한다.

입력

첫째 줄에 N이 주어진다. N은 항상 3•2^k 수이다. (0 ≤ k ≤ 10)

 

예제 입력

24

 

예제 출력

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

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 이 문제는 규칙을 찾아야 하는데 다음과 같은 규칙을 찾을 수 있다.

 

맨 위 꼭짓점을 기준으로 가운데, 왼쪽 아래, 오른쪽 아래로 같은 패턴이 그려지는 것을 알 수 있다.

 

그리고 또 다른 힌트는 입력이 3•2^k로 주어진다는 것이다.

 

이 말은 y를 기준으로 계속 반으로 나뉘어도 가장 작아지는 값이 3이라는 것이다.

 

즉, y를 계속 반으로 나누다가 3이 되었을 때가 기저사례가 되는 것이다.

 

그러면 다음과 같은 코드를 구할 수 있다.

코드

#include <iostream>

char map[3073][6145];

void solve(int N, int y, int x)
{
	if (N == 3)
	{
		map[y][x] = '*';
		map[y + 1][x - 1] = '*';
		map[y + 1][x + 1] = '*';
		for (int i = x - 2; i <= x + 2; i++)
			map[y + 2][i] = '*';
		return ;
	}
	solve(N / 2, y, x);
	solve(N / 2, y + N / 2, x - N / 2);
	solve(N / 2, y + N / 2, x + N / 2);
}

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 2 * N; j++)
			map[i][j] = ' ';
	}
	solve(N, 0, N - 1);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < (2 * N - 1); j++)
			std::cout << map[i][j];
		std::cout << "\n";
	}
	return 0;
}

문제 출처

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

2448번: 별 찍기 - 11