[Java/Python] 백준 2448번 - 별 찍기11 (골드 4)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 재귀

 

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

 

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N이 주어진다. N은 항상 $ 3×2^k $ 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

 

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

---

 

재귀는.. 어렵다...

 

우선 규칙을 찾아야 한다.

 

수는 3, 6, 12, 24, 48...로 늘어나며 모든 패턴은

 

 

 

위와 같이 나온다.

 

우리가 찾아야 할 것은 가장 맨 위 *을 찾는 것이다.

 

3일 때 *의 위치를 배열로 기준하면 (0, 2)

6일 때 *의 위치는 (0, 5)와 (3, 2), (3, 8)

12일 때 위치는 (0, 11) / (3, 8), (3, 14) / (6, 5) / (6, 17) / (9, 2) , (9, 8), (9,14), (9, 20) 임을 알 수 있다.

 

그 이후는 각 규칙에 맞춰 *을 그려주면 된다.

 

다만 아래의 Python 코드는 메모리초과가 발생하여.. java로 다시 제출하였다.

Python으로는 어떻게 해야 통과가 되는지 잘 모르겠다.

 

 

Python 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())

result = [[' ']*2*n for _ in range(n)]

def makeStar(x, y, size):
    if size == 3:
        result[x][y] = "*"
        result[x+1][y-1] = "*"
        result[x+1][y+1] = "*"
        for i in range(5):
            result[x+2][i+y-2] = "*"
    else:
        newSize = n//2
        makeStar(x, y, newSize)
        makeStar(x+newSize, y-newSize, newSize)
        makeStar(x+newSize, y+newSize, newSize)
        
makeStar(0, n-1, n)        

for star in result:
    print("".join(star))

 

Java코드

import java.io.*;
import java.sql.Timestamp;
import java.text.SimpleDateFormat;
import java.util.*;


public class Main {	
	
	static char[][] result;
	
	public static void makeStar(int x, int y, int size) {
		if(size == 3) {
			result[x][y] = '*';
			result[x+1][y-1] = '*';
			result[x+1][y+1] = '*';
			for(int i=0; i<5; i++) {
				result[x+2][i+y-2] = '*';
			}
		} else {
			int newSize = size/2;
			makeStar(x, y, newSize);
			makeStar(x+newSize, y-newSize, newSize);
			makeStar(x+newSize, y+newSize, newSize);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		result = new char[n*2][n*2];
		for(int i=0; i<n*2; i++) {
			for(int j=0; j<n*2; j++) {
				result[i][j] = ' ';
			}
		}
		makeStar(0, n-1, n);
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n*2; i++) {
			for(int j=0; j<n*2; j++) {
				sb.append(result[i][j]);
			}
			sb.append('\n');
		}
		System.out.println(sb);
	}
}